꼬리 재귀

재귀의 Stack Overflow문제를 해결하기 위한 방법인 꼬리 재귀에 대해서 알아보자.

우선 퀴즈를 하나 내어보겠다.
아래 함수가 재귀함수인지 아닌지 맞춰보길 바란다.

int foo ( int n ) {       if ( n == 0 ) {             return 1;       }       return 2 * foo ( n - 1 ); }

n=2라고 하면
foo(2) = 2*foo(1) = 2*2*foo(1) = 2*2*1 = 4
의 식으로 foo(0)이 될때까지 재귀를 반복한다.

따라서 이는 재귀함수라고 볼 수 없다.


그러면 꼬리재귀함수는 어떤 모양일까?

가장 쉬운 예를 들기 위해
앞의 글에서 얘기했던 최대공약수를 다시 예로 들어보겠다.

만약 최소공약수 구하는 함수를 꼬리재귀로 구현한다면 아래와 같을 것이다.

int gcd ( int m, int n ){       if ( n == 0 ){             return m;       }       else{             return gcd ( n, m%n );       } }

위는 그 어떠한 재귀나 m=n같은 대입과정 없이
최대공약수를 Stack 활용 없이 아주 깔끔하게 구현한 코드이다.

m=40, n=30이라고 가정해보자.
gcd(40,30) = gcd(30,10) = gcd(10,0) = 10

단 3단계의 계산만으로 10이라는 최대공약수가 도출되었다.
그리고 return 이후 다시 돌아오는 과정 또한 없다.

꼬리 재귀인 것이다.