재귀 vs 꼬리 재귀

재귀(Recursion)

함수 내에서 자기 스스로를 호출하는 함수를 재귀 함수라고 한다.

그리고 함수형 프로그래밍에서 불변성(Immutable)을 유지하기 위해서 재귀를 사용한다.

 

불변성(Immutable)은 함수형 코드의 핵심적인 속성이다. 프로그램의 변경 가능한 상태가 적을수록 프로그래머가 프로그램을 작성하는 동안 고민할 대상이 줄어들게 된다. 다수의 프로그래밍 오류는 프로그래머가 변경하는 세부사항을 대량으로 동시에 유지할 수 없기 때문에 발생한다. 상태를 변경하면 반드시 이를 추적하고 관리해야 하는 복잡함이 발생한다.

 

재귀를 사용하면 프로그래머가 신경 써야 하는 변수가 줄어든다. 그리고 재귀가 호출되면서 변경되는 값들이 복사를 통해서 전달된다. 불변성을 유지하는 방법은 매번 값을 복사하는 것이다.

 

재귀를 사용하면 함수를 여러 번 호출하게 된다. 이때 메모리엔 어떤 변화가 생길까? 우선 함수가 한 번씩 호출될 때마다 함수의 입력값(매개변수), 결괏값(리턴값), 그리고 리턴 후 돌아갈 위치 등이 스택(Stack)이라는 데이터 저장 공간에 보관된다.

 

그런데 재귀는 호출의 호출의 호출의 호출.... 을 반복하기 때문에 무수히 많이 호출하면 이 스택이라는 공간이 다 차버려서 '스택 오버 플로우' 현상이 일어나게 된다.

 

 

아래와 같은 재귀함수를 호출하면 무한히 호출하다가 스택 영역이 초과되면서 에러를 반환한다.

class Program
{
    static void Main(string[] args)
    {
        Bar();
    }

    static void Bar()
    {
        Bar();
    }
}

꼬리 재귀(Tail-Recursion)

재귀 함수의 장점은 그대로 살리고, 스택 오버 플로우가 일어나는 단점을 보완하는 방법이 바로 '꼬리 재귀'이다.

 

C# 꼬리 재귀(tail recursion)

 

일반 재귀 팩토리얼

int factorial(int n)
{
    if(n == 1) return 1;
    return n * factorial(n - 1);
}

 

꼬리 재귀 팩토리얼

int factorialTail(int n, int acc)
{
    if(n == 1) return acc;
    return factorialTail(n - 1, acc * n);
}

int factorial(int n){
    return factorialTail(n, 1);
}

 

팩토리얼 함수가 두 개로 분리되었다. 요점은 재귀 호출 이후에 추가적인 연산을 요구하지 않도록 구현하는 것이다.

 

일반 재귀 팩토리얼은 추가 연산이 존재한다.

일반 재귀로 구현한 factorial 함수는 재귀 호출을 하고 나서 num을 곱하는 연산이 존재한다.

따라서 일반 재귀로 구현된 함수는 아래 함수와 같이 동작한다.

 

int factorial(int num)
{
    if(num == 0) return 1;
    int callResult = factorial(num - 1);
    return num * callResult;			// 재귀 호출 이후 추가적인 연산이 필요하다.
}

 

반면 꼬리 재귀로 구현된 함수는 호출 이후에 연산이 없다.

 

int FactorialTail(int n)
{
    int acc = 1;
    
    do{
        if(n == 1) return acc;
        acc = acc * n;
        n = n - 1;
    } while(true);
}

 

이렇게 내부적으로 재귀 함수를 반복문으로 변경해서 실행하기 때문에 스택도 여러 번 쌓이는 게 아닌 한 번만 호출된다.

참조 사이트

재귀함수와 꼬리 재귀