꼬리 재귀 (Tail Recursion)

1. 꼬리 재귀

• 재귀 호출이 끝나면 아무것도 하지 않고 리턴하는 방법 
• 컴파일러 최적화에 의해 재귀 호출이 깊어져도 스택 프레임이 쌓이지 않고 재사용하기 때문에 빨라진다.

2. 예시

int Factorial(int n)
{
    if (n == 1)
        return 1;

    return n * Factorial(n - 1);
}

int FactorialTail(int n, int acc = 1)
{
    if (n == 1)
        return acc;

    return FactorialTail(n - 1, n * acc);
}

팩토리얼을 구하는 함수를 재귀방식, 꼬리 재귀 방식으로 작성해 보았다.

위 함수는 return statement에서 n * Factorial(n-1) 에 의해 재귀 호출을 빠져나가는 과정에서 * 연산을 해 주어야 한다.

하지만 꼬리 재귀로 구현한 경우 return문에서 아무 연산도 해 주지 않는다.

 

재귀 구현으로 자주 나오는 피보나치 수열도 꼬리재귀로 구현할 수 있다.

int FiboTail(int n, int prev = 1, int old = 0)
{
    if (n == 1)
        return old;
    if (n == 2)
        return prev;

    int tmp = old + prev;
    old = prev;
    prev = tmp;

    return FiboTail(n - 1, prev, old);
}