꼬리재귀(tail-recursion)와 꼬리 호출 최적화(TCO)

재귀함수를 사용할 때는 콜스택 증가로 인한 메모리 낭비, stack overflow 발생 위험을 조심해야 한다.
이 때 재귀함수를 꼬리재귀 형태로 작성할 수 있다면 이 문제를 회피할 수도 있다. 몇몇 언어에서(특히 함수형 언어)는 꼬리 호출 최적화(TCO: Tail-Call Optimization)를 지원하기 때문이다.

꼬리재귀(tail-recursion)

재귀함수의 리턴값이 재귀호출의 반환값인 상황을 꼬리재귀라고 한다.

꼬리 호출 최적화 (TCO: Tail call optimization)

TCO(Tail call optimization)는 꼬리재귀 함수 호출시 스택 프레임을 재사용하는 최적화 방식이다. 스택에 쌓인 호출 정보를 새로운 호출에 대한 것으로 업데이트하여 메모리 사용량을 줄일 수 있다.

꼬리 호출 최적화가 적용되는 조건
1️⃣ 함수의 구현이 꼬리재귀 형태를 띤다.
2️⃣ 해당 언어의 해석기(interpreter)가 꼬리 호출 최적화를 지원한다.

일반재귀 vs 꼬리재귀

일반재귀와 꼬리재귀의 차이점을 예제로 확인해보자.

// 일반 재귀
function count(n){ 
    return n <= 1 ? 1 : 1 + count(n - 1); // false절에 재귀호출 이외의 추가적인 연산(1 + )이 존재한다.
}

// 꼬리 재귀
function count(n) {
    function iter(sum) {
        return sum >= n ? sum : iter(sum + 1); // false절에 재귀호출구문만 존재한다.
    }
    return iter(0);
}

위의 두가지 count(n) 함수는 1을 n번 더해서 n을 반환하는 동작을 하는 함수이다.
두 함수는 같은 동작을 할 것으로 기대되지만 해석기가 이를 평가하는 과정에서 차이가 있다.

일반 재귀함수의 동작

function count(n){ 
    return n <= 1 ? 1 : 1 + count(n - 1);
}

count(4);

위의 일반재귀 함수호출 과정을 다음같은 치환모형으로 나타낼 수 있다.

count(4)
1 + count(3)
1 + (1 + count(2))
1 + (1 + (1 + count(1))
1 + (1 + (1 + 1))
1 + (1 + 2)
1 + 3
4

지연된 연산의 사슬형태를 특징으로하며 이런 과정을 가리켜 재귀적 과정(recursive process)이라고 부른다.

치환모형에 따라 완전히 전개된 후 축약이 일어나는 형태를 띠는데, 전개 과정에서는 콜스택이 쌓이며 축약 과정에서 콜스택을 제거하게 된다.

재귀호출 단계가 많아질수록 해석기가 기억해야 될 정보의 양이 (예시에서는 n에 비례하여 선형적으로)늘어나며, 콜스택이 과도하게 생성되어 stack overflow가 발생할 수 있는 위험이 있다.

꼬리 재귀함수의 동작

function count(n) {
    function iter(sum) {
        return sum >= n ? sum : iter(sum + 1); // false절에 재귀호출구문만 존재한다.
    }
    return iter(0);
}

count(4);

꼬리재귀 예시도 치환모형으로 나타내면 다음과 같이 진행된다.

count(4) // 아래 함수들이 매개변수 n=4를 외부변수로 참조하게된다
iter(0)
iter(1)
iter(2)
iter(3)
iter(4)
4

꼬리 재귀 케이스에서는 단계가 진행됨에 따라 식이 전개되거나 축약되지 않는다.

이러한 과정을 반복적 과정(iterative process)이라고 부르며 과정의 상태를 저장하는 고정된 개수의 상태변수, 상태 변수를 갱신하는 고정된 규칙, 과정을 종료하는 종료 판정 규칙으로 규정된다.

 

임의의 n에 대해 해석기는 각 단계에서 매개변수로 전달되는 sum(+ 외부변수 n)만 알고있으면 되므로 상위 콜스택을 기억할 필요가 없다. 이 점에 착안하여 재귀호출하는 함수 콜스택의 메모리를 재활용할 수 있다.

따라서 재귀호출 단계가 늘어나도 콜스택이 증가하지 않는다. (TCO 를 지원하는 엔진이라고 가정)

JavaScript에서의 꼬리재귀 최적화 지원

scheme의 표준에 따르면 scheme구현은 반드시 꼬리 재귀적이어야 한다.
JavaScript또한 scheme의 핵심적인 기능을 물려받아 렉시컬 스코프, 일급함수, 동적 형식적용 등의 설계 원칙들과 더불어 꼬리 재귀 해석방식을 ES6 표준으로 지정했다. (https://262.ecma-international.org/6.0/#sec-tail-position-calls)

[자바스크립트로 배우는 SICP]

C, 자바, 파이썬 등의 흔히 쓰이는 프로그래밍 언어에서는 재귀호출로 구현을 해도 TCO를 지원하지 않는반면 자바스크립트는 TCO를 지원한다고 한다.

... 정말 그럴까?

 

꼬리재귀함수 호출 테스트 in Chrome

 

Chrome 개발자 콘솔에서 꼬리재귀 함수를 실행해봤더니 stack overflow가 발생한다.

꼬리재귀 최적화가 되어있다면 stack overflow가 발생하지 않아야 할텐데... 어떻게 된걸까?

알고보니 ES6문서에는 꼬리 재귀 최적화 스펙이 표준으로 명시되어있기는 하나, 현재 대부분의 브라우저는 이 표준을 준수하지 않는다고 한다.

많은 주요 브라우저들이 사용하는 Blink의 V8엔진이 TCO를 지원하지 않기때문이다.

그래도 Webkit의 JavascriptCore엔진은 TCO 지원을 하기때문에 (https://webkit.org/blog/6240/ecmascript-6-proper-tail-calls-in-webkit/) Webkit 기반인 Safari에서는 꼬리 재귀 호출시 stack overflow가 발생하지 않는 것을 확인할 수 있다.

일반재귀함수(위), 꼬리재귀함수(아래) 호출 테스트 in Safari

 

여기서 한가지 주의할 점은 Webkit 기반 브라우저를 사용할 때에도 "use strict" 를 꼭 명시해줘야 TCO를 지원한다는 것이다.

---

개인적으론 Chrome이 제일 표준을 잘 지킬거라는 믿음이 있었는데..(대부분의 경우 그렇다) Chrome이 지키지 않은 스펙을 Safari가 지켰다는게 놀라웠다.

ES6 스펙이 나온지는 현재시점(2024년) 기준으로 9년이 되었는데도 Blink가 해당 스펙을 지원하지 않는 것보면, 해당 기능 지원에 대한 우선순위가 낮다고 판단한 모양이다. 아무래도 직접적인 사용자 인터페이스와 관련된 표준은 아니어서일까?

 

그리고 여태 use strict는 자바스크립트 특유의 느슨한 rule로 작성된 코드에 대해 syntax 오류를 발생시키는 역할정도만 수행한다고 생각했는데, 해석기 내부의 최적화 로직까지 달라지는 케이스를 처음 발견해서 신기했다.

 

실무에서 tail-recursion 함수를 만들어 사용할일이 있을지는 모르겠다. 아무래도 재귀함수는 가독성이 떨어지기도 하고, 그냥 for loop 사용하면 해결되는 문제아닌가? 함수형 프로그래밍 방식에 집착해야되는 케이스가 아니라면..

그래도 리턴타입의 형식을 감지해서 상위 콜스택 메모리를 재활용하는 방식의 최적화 아이디어는 주목할만한 것 같다. 추후에 다른 시스템 설계할 때 응용해볼 수 있지 않을까.