[재귀] 재귀 vs 꼬리 재귀

[재귀] 재귀 vs 꼬리 재귀

재귀와 꼬리 재귀의 차이

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

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

꼬리 재귀로 구현하게 되면 위 문제가 해결된다. 코드 상에서 해결되는 건 아니고 컴파일러가 꼬리 재귀를 인식하고 코드를 최적화 하면서 일반 재귀가 가지는 단점을 없애준다. 꼬리 재귀는 재귀 함수를 원래 함수의 꼬리 부분에서 호출하는 경우를 말하는데 컴파일러는 꼬리 재귀로 작성된 코드를 인식해서 반복문으로 바꿔준다. 아래 코드를 보자.

Code

#include <stdio.h>
 
//***** 일반 재귀 *****//
int FactorialRec(int n){
    if (n == 1)
        return 1;
    else
        return n*FactorialRec(n - 1);
}
 
//***** 꼬리 재귀 *****//
int FactorialTailRec(int n, int res){
    if (n == 1)
        return res;
    return FactorialTailRec(n - 1, res*n);
}
 
int FactorialTail(int n){
    return FactorialTailRec(n, 1);
}
 
//***** 꼬리 재귀 -> 반복문 *****//
//***** 컴파일러 최적화시 변경된 코드 *****//
int FactorialTailRecLoop(int n){
    int res = 1;
    for (; n > 0; n--){
        res = res * n;
    }
    return res;
}
 
int main(int arc, char** argv){
    printf("%d\n", FactorialRec(5));
    printf("%d\n", FactorialTail(5));
    printf("%d\n", FactorialTailRecLoop(5));
}

주의점

꼬리 재귀 구현 부분이 일반 재귀랑 같게 실행이 될 수 있다. 이 경우는 컴파일 옵션에서 코드 최적화가 되도록 설정해 주어야 한다.(gcc 컴파일러는 O3 최적화 옵션 적용)

결론

꼬리 재귀는 결국 반복문 실행이기 때문에 일반 재귀 함수에서 발생하는 스택 오버 플로우나 성능저하가 발생하지 않는다. 재귀의 탈을 쓰고 있는 반복문이기에 가독성과 성능 모두 만족시킨다. 하지만 컴파일러에서 최적화 해주지 않는다면 꼬리 재귀 자체의 이점은 사라진다. 따라서 컴파일러에서 최적화가 되는지 확인 후 사용해야 한다.

성능만 본다면 재귀함수는 사용하지 않는게 맞다. 반복문으로 구현했을 때 보다 메모리나 속도 등 성능적인 측면에서 많이 뒤쳐지기 때문이다. 하지만 예전처럼 H/W가 좋지 못해 S/W 속도를 극한까지 끌어올려야 하는 시대가 아니기에 가독성도 고려해 프로그래밍을 해야한다.(재귀로 구현하면 간단한 코드가 반복문으로 구현하면 매우 복잡해 지는 경우가 많다. 궁금하면 하노이탑 문제를 반복문으로 구현해 보면 이 말을 이해할 것이다.) 특히 여러 사람이 개발에 참여한다면 가독성은 더욱 중요하다. 본인의 프로그램의 목적에 맞게 판단해서 사용해야 하겠다.