꼬리 재귀 최적화

꼬리 재귀 최적화 Tail Recursion Optimization은
일반 재귀함수를 꼬리 재귀로 바꾸어 메모리 사용을 최적화하는 것을 말한다.

꼬리 재귀 함수

함수를 실행하고 반환값에 추가적인 연산이 없는 재귀함수를 말한다.

꼬리 재귀 함수 최적화 조건

1. 재귀함수가 꼬리 재귀함수형태여야 한다.
2. 컴파일러가 꼬리 재귀함수 최적화를 지원해야한다.

꼬리 재귀 vs 일반 재귀

자바 팩토리얼 구현을 보며 꼬리 재귀와 일반 재귀의
차이에 대해서 알아보자.

# Tail.java

public class Tail{
    public static void main(String[] args){
        System.out.println(factorial(5));
        System.out.println(factorialTail(5, 1));
    }

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

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

왜 꼬리 재귀는 최적화가 되는 걸까?

꼬리 재귀의 경우 지금 함수의 계산결과만을 반환하면 되기 때문에
재귀로 여러번 함수를 호출해도 이전 함수의 결과만 기억하면 되기 때문에
꼬리를 물며 선형적으로 계산할 수가 있다.
그래서 gcc같은 꼬리 재귀를 지원하는 컴파일러의 경우
스택 메모리에 저장할 때 함수가 호출될 때마다 새로 할당하는 게 아니라
하나의 메모리 공간에 덮어쓰며 재사용하는 방식으로 연산을 하게 된다.