[Algorithm] Tail Recursion (꼬리 재귀)

재귀 함수

재귀 함수는 '기저 사례(base case)'와 '재귀적 관계(recurrence relation)'만 알면 정말 간단하게 구현할 수 있다. 그리고 보통 코드가 짧아서 가독성도 좋다.

• 쪼개지지 않는 가장 작업들을 가리켜 재귀 호출의 기저 사례(base case)
• 자기 자신과 관계를 맺는 형식을 재귀적 관계(recurrence relation)

하지만 장점이 있으면 단점도 있는 법이다.

재귀 호출을 할 때마다 콜 스택에 새로운 프레임이 쌓이고, 각 프레임은 지역 변수나 인수를 저장하기 위해 메모리를 사용한다. 이게 보통은 문제가 되지 않지만, 만약 각 프레임에서 기가바이트 단위의 데이터를 받아 처리해야 하는 경우에는 문제가 심각해질 수도 있다. 혹은 콜 스택이 너무 깊어지면 스택 공간이 가득차 스택 오버플로우(stack overflow)가 발생할 수 있다.

위 단점을 보완하기 위해 사용할 수 있는 방법이 'Tail Recursion'이다.

 

Tail Recursion (Tail Call Optimization, TCO)

Tail recursion에서 재귀 호출은 제일 마지막 인스트럭션이고, 단 한 번만 호출된다.

재귀 호출이 가장 마지막 인스트럭션이기 때문에 재귀 함수의 결과를 받은 후, 함수에서는 더이상 할 일이 없다. 할 일도 없는데 콜 스택에 프레임을 두는 것은 메모리 낭비다.

따라서 매 호출마다 새로운 프레임을 생성하는 것보다 이미 있는 것을 재사용하는 것이 효율적이다. 프레임을 재사용하면 콜 스택이 깊어지지 않기 때문에 스택 공간을 효율적으로 사용할 수 있다. 이 원리를 사용하는 것이 tail recursion이다.

Tail recursion의 최적화는 컴파일러가 감지해 알아서 해준다. 하지만 컴파일러가 TCO를 지원하지 않는다면 최적화는 일어나지 않는다.

pow

거듭제곱을 해주는 함수인 pow를 예시로 최적화를 해보자.

아래는 일반적인 재귀 함수로 구현한 거듭제곱 함수다.

function naivePow(x, n) {
    if(n === 0) return 1;
    return x * naivePow(x, n - 1);
}

위 함수는 재귀 호출의 결과를 사용해 연산을 추가적으로 해야하기 때문에 n 깊이만큼 콜 스택이 쌓인다.

이제 tail recursion을 적용해보자.

function optimizedPow(x, n) {
    function helper(x, n, acc) {
        if(n === 0) return acc;
        return helper(x, n - 1, acc * x);
    }
    return helper(x, n, 1);
}

이제는 재귀 호출 이후 해야할 연산이 하나도 없기 때문에 콜 스택이 깊어질 이유가 없다. 따라서 TCO가 적용된다면 프레임을 재사용하게 된다.

 

자바스크립트 TCO 지원

크롬의 V8 엔진과 대부분의 자바스크립트 엔진들이 TCO를 지원하지 않는다고 한다. 현재는 사파리가 유일하게 TCO를 지원하는 브라우저다.

실제로 위에서 구현한 optimizedPow에 n 값을 크게주면 바로 스택오버플로우를 만날 수 있다.

자바스크립트의 재귀함수는 스택오버플로우를 피할 수 없을까?

TCO처럼 동작하게 만들기

한 번 optimizedPow가 TCO가 적용된 것처럼 동작하게 수정해보자.

콜 스택이 쌓이지 않으려면 재귀 호출이 아닌 iterative하게 접근할 수 밖에 없다. Iterative하게 접근하기 위해서는 helper가 자기자신을 호출하지 못하게 해야한다. 그러기 위해서 이제 helper는 함수를 반환한다.

function optimizedPow(x, n) {
    const helper = (x, n, acc)  => () => {
        if(n === 0) return acc;
        return helper(x, n - 1, acc * x);
    }
    // ...
}

이제 helper를 통해 원하는 결과를 얻어야 한다. helper를 통해 얻은 함수를 실행하면 또 다른 함수를 얻거나 결과(acc)를 얻을 수 있으니, 결과를 얻을 때까지 함수를 계속 실행해주자.

function optimizedPow(x, n) {
    const helper = (x, n, acc)  => () => {
        if(n === 0) return acc;
        return helper(x, n - 1, acc * x);
    }

    let val = helper(x, n, 1);
    while (typeof val === "function") {
        val = val();
    }
    return val;
}

물론 이제 재귀함수라고 할 수 없지만, 얼추 모양은 비슷하게 유지하면서 val이 한 번씩 호출되기 때문에 더이상 콜 스택도 깊어지지 않는다.

이제 아까 작성한 함수보다 훨씬 큰 n 값을 다룰 수 있게 됐다.