재귀함수 for문 - jaegwihamsu formun

알고리즘 문제를 풀면서 DFS, DP, Brute Force, Combination 등의 문제를 풀다 보면 간혹 의문이 생긴다. 나는 보통 위와 관련된 알고리즘 문제를 풀 때 재귀함수 를 이용한다. 문제에 따라 달라지긴 하겠지만 반복문, 재귀함수 모두 구현이 가능한것으로 알고있다. 습관적인 부분도 있겠지만 반복문 으로 생각하다가 재귀함수로 바꿔서 푸는 경우도 많았고 그냥 편하다 재귀함수 로 푸는 것이. 왜 그럴까? 반복문 과 재귀함수 의 차이를 알아보자. 

https://wonillism.tistory.com/20

[Programmers - lv02] 피보나치 수 (cpp / python)

피보나치 수 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.

wonillism.tistory.com

피보나치 수를 이용하여 직접 풀어본 포스팅입니다. 이해가 잘 안된다면 참고 하세요.

반복문(Iteration) :

• 기본 : 일련의 명령을 반복적으로 실행할 수 있다
• 체재 : 반복에는 초기화, 조건, 루프 내의 명령문 실행 및 제어 변수 업데이트가 포함
• 종료 : 특정 조건에 도달 할 때까지 반복적으로 실행
• 조건 : 반복문의 제어 조건이 참이라면 무한 반복이 발생
• 무한반복 : 무한 루프는 CPU 사이클을 반복적으로 사용
• 스택 메모리 : 스택 메모리를 사용하지 않음
• 속도 : 빠른 실행
• 가독성 : 코드 길이를 더 길게 만들고 변수가 많아 가독성이 떨어짐

재귀함수(Recursion)

• 기본 : 함수 자체를 호출 한다
• 체재 : 기본적으로 종료 조건만 지정 한다 (조건이 추가 될 수도 있음)
• 종료 : 조건부 문은 함수 호출 본문에 포함되어 재귀 호출을 실행하지 않고 함수를 강제로 반환한다
• 조건 : 기본적으로 조건에 수렴하지 않으면 무한 재귀가 발생한다
• 무한반복 : 무한 재귀는 스택 오버플로우를 일으킴
• 스택 메모리 : 스택 메모리는 함수가 호출 될 때마다 새 로컬 변수와 매개 변수 집합을 저장하는데 사용
• 속도 : 느린 실행
• 가독성 : 코드 길이와 변수가 적어 가독성이 높아짐

위의 차이만 본다면 재귀함수와 반복문 중 알고리즘을 작성하는데 있어서는 반복문이 더 낫지않을까 싶다.
재귀 호출이 중요한 이유는 크게 봐서 두 가지 인 것같다.

• 알고리즘 자체가 재귀적인 표현이 자연스러운 경우
• 변수 사용 을 줄일 수 있다.
  변수 사용을 줄여준다는 것은 변수가 잡는 메모리에 대한 이야기가 아니라, mutable state(변경 가능한 상태) 를 제거하여 프로그램 오류가 발생할 수 있는 가능성을 줄인다는 이야기이다. 단순한 경우에는 오히려 재귀호출이 직관적으로 이해하기 어려울 수도 있지만, 프로그램이 복잡해지면 mutable state 를 최대한 피하는 것이 오류 없는 프로그램을 짜는 데에 중요한 원칙이 된다.

mutable state 를 최대한 피하는 것은 변수의 수를 줄이는 것과 변수가 가질 수 잇는 값의 종류 또는 범위를 정확히 제한하는 것이라고 생각하면 된다.

아래 두 코드를 보자.
프로그램 1

    int sum = 0;
    for(int i = 0; i <= 100; ++i) {
        sum += i;
    }
    printf("%d\n", sum);

프로그램 2

    int sum(const int x, const int acc) {
    if(x > 100) return acc;
    else return sum(x + 1, x + acc);
    }

    printf("%d\n", sum(0, 0));

둘 다 0부터 100까지의 합을 구하는 프로그램이다.
그런데 프로그램1에는 변수가 두 개 있고, 프로그램2에는 변수가 하나도 없다. (프로그램2에서 x와 acc는 변수가 아님, 값이 바뀔 수 없다.) 그리고 이 경우에는 tail recursion이기 때문에 컴파일러가 똑똑하다면 루프를 사용하는 경우와 동일한 성능을 보장할 수 있고 stack overflow도 없다.

재귀 vs 꼬리 재귀

그렇다면 재귀와 꼬리재귀는 무엇일까?
함수를 호출하면 함수가 호출된 위치를 주소 값이 저장되어야 한다. 함수가 재귀적으로 호출될 경우 함수 안에서 함수가 계속해서 호출되고 차례로 리턴된다. 그래서 호출 횟수가 많아지면 돌아갈 곳의 주소 값을 저장하고 잇는 스택이 넘치거나 프로그램의 실행 속도가 느려진다.

위 문제는 함수가 호출된 위치를 기억하기 때문에 발생한다. 일반적인 재귀 함수의 경우 리턴되는 함수 값을 받아 연산을 하고 다시 그 값을 리턴하는 방식을 취한다. 그렇다면 함수가 호출된 위치로 돌아갔을 때 실행할 작업이 없다면? 함수 호출 위치를 기억할 필요도 없고 스택 오버플로우도 없지 않을까?

꼬리 재귀 가 이 문제를 해결할 수 있는 방법이다. 컴파일러가 꼬리 재귀 최적화 를 지원한다면 성능 및 메모리의 이점을 얻을 수 있다.

int Recursive(int n) 
{
    if(n==1) return 1;
    return n + Recursive(n-1);
}
int Tail_Recursive(int n, int acc)
{
    if(n==1) return acc;
    return Tail_Recursive(n-1, n + acc );
}

일반 재귀는 함수의 마지막, return에 연산이 필요하다. (n + 함수(n-1))
꼬리 재귀는 return에 연산이 필요없다. 매개변수로 필요한 연산을 전달한다. (함수(n-1, n+acc))
여기서부터 꼬리 재귀의 이점은 컴파일러가 지원한다. 컴파일러가 꼬리 재귀를 최적화 할 수 있으면 최적화 하는 과정에서 꼬리 재귀를 반복문으로 변경한다.
따라서 기존 재귀의 문제였던 메모리와 성능에 대한 문제가 제거되는 것이다.

결론

성능 측면에서만 본다면 재귀함수는 사용하지 않는 것이 맞다. 반복문으로 구현했을 때 보다 메모리나 속도 등 성능적인 측면에서 많이 뒤쳐지기 때문이다. 하지만 예전처럼 Hardware가 좋지 못해 Software의 속도를 극한까지 끌어올려야 하는 시대가 아니기 때문에 가독성도 고려하여 프로그래밍을 해야한다. 특히 여러사람이 개발에 참여한다면 가독성은 더욱 중요하다. 결국 프로그램의 목적에 맞게 판단해서 사용해야한다.

지금까지 반복적인 작업이 필요한 알고리즘 문제들(거의 필연적인..?)을 풀면서 일반 반복문(while, for)이나 재귀함수를 번갈아가며 사용했었다. 하지만 코드나 접근방식에 오류가 생겼을 때, 발생하는 현상은 달랐다.

일반 반복문은 시간 초과(무한 루프), 재귀함수는 stack overflow가 발생했다.

재귀함수의 경우 stack이라는 메모리 공간을 계속 이용하기 때문에 메모리의 제한이 있는 한 stack overflow가 뜨면서 메모리가 터진다고 한다. 반복문의 경우에는 메모리를 이런식으로 사용하지 않아 단지, 프로그램이 종료되지 않을 뿐이다.

그렇다면 재귀함수의 경우 반복문에 비해 메모리를 많이 사용한다는 확연한 단점을 가지고 있는데 왜 자주 사용하게 될까? (사실 나 또한 while이 어색해서 재귀함수를 많이 쓰곤한다..ㅎ) 한번 알아보도록 하자!

반복문과 재귀함수

프로그램은 반복되는 작업을 수행하도록 설계된다. 따라서 반복을 구현하는 로직은 필수적이고 프로그래밍 언어마다 for, while 같은 기본적인 반복 제어문을 지원한다. 즉 반복문의 정의는 명령을 반복적으로 실행하는 것 그 자체다.

이때 반복되는 작업은 기본 반복 제어문뿐 아니라 재귀함수로도 구현할 수 있다.

재귀함수의 정의는 하나의 함수가 자신을 다시 호출하여 반복되는 작업을 수행하는 함수다. 

반복문 vs 재귀함수

처음 의문점의 답을 알기 전에 반복문과 재귀함수의 차이점에 대해 알아보자.

※ 스택오버플로우(stack overflow)란?
재귀함수 사용 시, 함수를 반복적으로 호출하므로, 스택메모리에 콜 스택이 쌓이게 된다. 이때 함수를 호출하는 횟수가 많아진다면 스택메모리를 초과하여 stack overflow가 발생하는 것이다. (일반적인 반복문 사용 시, 지역 변수들이 호출될 때 한번만 할당되기 때문에 이러한 일이 발생하지 않는다.)

왜 재귀함수를 사용할까?

아무리 봐도 단점밖에 보이질 않는 재귀함수! 느리고.. 메모리를 사용하고..

그럼에도 불구하고 재귀함수를 사용하는 이유는 무엇일까?

1. 변수 사용을 줄일 수 있다.

변수 사용이 줄어든다는 뜻은 프로그램에 오류가 생길 가능성이 줄어들고, 프로그램이 정상적으로 돌아가는지에 대한 증명이 쉬워진다는 뜻이다.

일반 반복문

let sum = 0;
for(let i = 0; i <= 100; i++) {
  sum += i;
}

재귀 함수

function sum(x) {
  if(x === 100) return x;
  else return x + sum(x + 1);
}

sum(0)

위의 코드들은 전부 0부터 100까지의 합을 구하는 코드다.

일반 반복문의 경우 sum, i 라는 2개의 변수를 가지고

재귀 함수의 경우 x라는 1개의 변수를 가진다.

사실 지금은 별 차이가 없어보이지만 좀 더 많은 변수를 사용할 일이 생길 때 조금이나마 변수를 줄일 수 있다. 이를 통해 예상치 못한 side effect 를 막을 수 있다!

2.   알고리즘 자체가 재귀적인 표현이 자연스러운 경우 (+ 가독성)

재귀함수하면 너무나 유명한 예시인 피보나치 수열은 1, 1, 2, 3, 5, 8 ... 의 값을 가지는 데 이를 식으로 나타내보자면 다음과 같다.

f(n) = f(n - 1) + f(n - 2)

일반 반복문

function fibonacci(n) {
  let pre = 0;
  let cur = 1;
  let last = 0;
  for(let i = 1; i < n; i++){
    last = pre + cur;
    pre = cur;
    cur = last;
  }
  return last;
}

재귀 함수

function fibonacci(num) {
  if(num < 2) return num;
  return fibonacci(num - 1) + fibonacci(num - 2);
}

위의 두 예시를 비교해보자면 재귀 함수의 경우 더욱 직관적임을 알 수 있다! 사실 알고리즘을 풀 때 재귀함수를 자주 사용했던 이유들을 생각해보면 가독성이 좋다는 이유가 가장 컸던 것 같다!

꼬리 재귀

재귀 함수또한 여러 장점들을 가지고 있지만 메모리를 많이 사용한다는(+ stack overflow)라는 큰 문제점을 갖고 있는데.. 이러한 단점을 보완하고자 꼬리 재귀 기법이란 것이 나왔다!

(단, 컴파일러가 꼬리 재귀 최적화를 지원해야만 실질적으로 단점을 보완할 수 있다.)

아래 일반 재귀, 꼬리 재귀 코드를 보도록 하자.

// 일반 재귀
function sum(x) {
  if(x === 100) return x;
  else return x + sum(x + 1);
}

sum(0)

// 꼬리 재귀
function tailSum(x, answer) {
  if(x > 100) return answer;
  else return tailSum(x + 1, answer + x)
}

tailSum(0, 0)

두 함수의 큰 차이는 다음 호출을 위한 파라미터의 연산이 어디에서 일어나는가? 이다.

일반 재귀의 경우 함수가 return 된 후에 연산이 일어나고 

꼬리 재귀의 경우 return 문 이전에 연산이 일어난다.

즉, 차이점은 return 문에 연산이 있냐 없냐이다.

꼬리 재귀가 호출되는 시점에 컴파일러는 꼬리 재귀를 최적화하고, 이 때 꼬리 재귀는 반복문으로 변경된다. 이를 통해 기존의 문제였던 메모리와 성능에 대한 단점을 해결할 수 있게 되었다.

정리

재귀 함수를 사용하여 반복 구조를 구현하면 복잡한 문제도 직관적으로 알 수 있고, 이는 협업에서 코드의 가독성이라는 이점이 될 수 있다. 하지만 콜 스택이 쌓여 stack overflow로 인한 메모리의 폭발이 일어날 수 있다는 단점을 가지고 있다. 이는 꼬리 재귀라는 기법을 통해 대비할 수 있지만, 무작정 방심할 수는 없다. 따라서 재귀 함수를 사용할 때 어느정도 함수를 호출하게 될 지 예측을 하고 안전하게 사용하는 것이 좋을 것 같다!