재귀 함수

재귀 함수는 자기 자신을 호출하는 함수입니다. 점화식과 비슷한데, 예시를 보면 좀 더 잘 이해할 수 있습니다.

#include <stdio.h>
int fibo(int a) {
      return (a < 3) ? 1 : fibo(a - 1) + fibo(a - 2);
}
int main() {
      for(int i = 1; i < 7; ++i)
            printf("fibo(%d): %d\n", i, fibo(i));
      return 0;
}

fibo(1): 1
fibo(2): 1
fibo(3): 2
fibo(4): 3
fibo(5): 5
fibo(6): 8

이름에서 눈치챘을 수도 있겠지만, 이 함수는 피보나치 수열의 a항을 구해주는 함수입니다. a3 미만, 즉 12이라면 1을 반환하고, 그렇지 않다면 전 항과 전의 전 항을 반환합니다. 그런데, 이 피보나치 수열 함수는 조금 느리게 움직입니다.


잘 보면, fibo(a)를 구하기 위해 호출하는 함수의 갯수가 fibo(a)에 비례해서 커집니다. fibo(a)1.618a에 비례해 커지므로, 결론적으로 fibo(a)를 구하기 위해 걸리는 시간은 1.618a에 비례해 커집니다. 조금 더 개선할 수 있을 것 같습니다.

int fibo(int a) {
      static int size = 3, arr[ 100 ] = { 0, 1, 1, 0, };
      if(a >= size) {
            arr[ a ] = fibo(a - 1) + fibo(a - 2);
            ++size;
      }
      return arr[ a ];
}

자, 이렇게 하면 배열에 이미 구해둔 값들을 저장해 놓으니까 좀 낫죠? 이미 구한 값은 바로바로 꺼내서 쓸 수 있고. 이런 것을 메모이제이션이라 합니다. 여기서는 걸리는 시간이 a에 비례해서 커지겠군요. 그런데 여기서 문제가 생겼습니다. 수가 많아지다 보니, arr[ 100 ]으로는 모자라는 경우가 생겼습니다. 200으로 늘렸지만 한참 모자랍니다(사실 94항만 해도 unsigned long long의 최대 크기인 264 - 1을 넘어갑니다). 어떻게 해야 할까요?

#include <stdio.h>
int fibo(int n, int a, int b) {
      return (n == 1) ? b : fibo(n - 1, b, a + b);
}
int main() {
      for(int i = 1; i < 7; ++i)
            printf("fibo(%d): %d\n", i, fibo(i, 0, 1));
      return 0;
}

fibo(1): 1 
fibo(2): 1 
fibo(3): 2 
fibo(4): 3 
fibo(5): 5 
fibo(6): 8

일반적으로 같은 일을 하는 재귀 함수와 반복문 중 속도가 더 빠른 것은 반복문입니다. 함수 호출에 따른 오버헤드가 없기 때문입니다. 하지만 컴파일러는 return 뒤에 수식(연산자) 없는 값이 오면 꼬리 재귀 최적화라고 불리는 것을 해 주는데, 이것을 통해 재귀 함수는 반복문과 동등한 수준의 속도를 얻게 됩니다(물론 반복문 쪽이 약간 더 빠릅니다). 이 코드는 꼬리 재귀를 사용할 뿐만 아니라, ab 두 변수에만 전 항과 전의 전 항을 저장해 메모리를 아낍니다. 이런 기법을 슬라이싱이라고 합니다. 하지만 두 번째 코드는 fibo(10)을 구한 후 추가적인 함수 호출 없이 fibo(5)를 구할 수 있었지만, 이번 코드는 얄짤 없이 처음부터 계산해야 합니다. 장단점이 있지요.

특정 작업들은 재귀함수를 사용하면 아주 쉽게 해결이 가능한 경우가 있습니다. 하지만 재귀 함수를 사용하는 알고리즘은 일반적으로 느리고(같은 부분을 여러번 계산하기 때문), 또 설령 같은 알고리즘으로 동작한다 해도 함수 호출에 의한 오버헤드가 발생합니다. 꼬리 재귀 최적화도 아무 컴파일러나 해 주는 것이 아닙니다. 반복문으로도 해결 가능한 작업이라면, 반복문을 사용해 주세요.

조금 더 머리를 굴리면 log a에 비례한 시간만으로도 fibo(a)를 구할 수 있습니다(사실은 log2a지만, 밑 변환을 해 주면 상수배입니다). 또, C++이라는 언어에서는 a1이던 100이던 같은 시간 안에 fibo(a)를 출력할 수 있습니다(물론 여기서 말하는 시간은 컴파일하는 데 걸리는 시간을 제외한 것입니다). 잘 고민해 보세요!