
재귀함수가 스택 안 터지고 10만 번 도는 법 (Tail Call Optimization)
재귀의 치명적 단점인 '스택 폭발'을 막는 기술. 바통 터치만 하고 퇴근하는 똑똑한 함수들 이야기.

재귀의 치명적 단점인 '스택 폭발'을 막는 기술. 바통 터치만 하고 퇴근하는 똑똑한 함수들 이야기.
내 서버는 왜 걸핏하면 뻗을까? OS가 한정된 메모리를 쪼개 쓰는 처절한 사투. 단편화(Fragmentation)와의 전쟁.

미로를 탈출하는 두 가지 방법. 넓게 퍼져나갈 것인가(BFS), 한 우물만 팔 것인가(DFS). 최단 경로는 누가 찾을까?

이름부터 빠릅니다. 피벗(Pivot)을 기준으로 나누고 또 나누는 분할 정복 알고리즘. 왜 최악엔 느린데도 가장 많이 쓰일까요?

매번 3-Way Handshake 하느라 지쳤나요? 한 번 맺은 인연(TCP 연결)을 소중히 유지하는 법. HTTP 최적화의 기본.

함수형 프로그래밍에 심취했던 시절, 저는 모든 반복문을 재귀(Recursion)로 대체하려는 객기를 부렸습니다.
for 문은 명령형(Imperative)의 시대착오적 유물처럼 보였고, 재귀야말로 선언형(Declarative)의 우아함이라고 믿었죠.
그러다 팩토리얼 10,000을 계산하는 코드를 돌렸을 때, 브라우저가 뻗어버렸습니다.
RangeError: Maximum call stack size exceeded
아름답게 짰던 제 코드는 메모리 폭식 괴물이 되어 있었습니다.
"루프는 10만 번을 돌아도 멀쩡한데, 왜 재귀는 몇천 번만 돌아도 터지는 걸까?" 이 질문이 저를 꼬리 재귀 최적화(TCO)의 세계로 이끌었습니다.
재귀 함수는 호출될 때마다 메모리에 스택 프레임(Stack Frame)이라는 흔적을 남깁니다. 이 프레임에는 지역 변수, 매개변수, 그리고 돌아갈 주소(Return Address)가 저장됩니다.
일반적인 팩토리얼 함수를 봅시다.
function factorial(n) {
if (n === 1) return 1;
return n * factorial(n - 1);
}
factorial(5)가 실행되는 과정을 스택 관점에서 보면 이렇습니다.
factorial(5)
┕ 대기 중: 5 * ...
factorial(4)
┕ 대기 중: 4 * ...
factorial(3)
...
factorial(5)는 factorial(4)가 끝날 때까지 집에 못 갑니다. 자기가 해야 할 곱셈(5 * ?)이 남아있거든요.
이렇게 함수들이 줄줄이 비엔나처럼 엮여서 메모리를 점유합니다. 깊이가 깊어지면 스택 메모리가 꽉 차서 폭발(Overflow)합니다.
만약 함수가 "나는 더 이상 할 일이 없으니, 다음 녀석이 한 일을 내 결과로 쳐라"라고 말하고 퇴근할 수 있다면 어떨까요? 이게 바로 꼬리 호출(Tail Call)의 핵심입니다.
코드를 이렇게 바꿔봅시다.
function factorialTail(n, total = 1) {
if (n === 1) return total;
return factorialTail(n - 1, n * total); // 꼬리 위치!
}
차이점이 보이시나요?
이전 코드: return n * factorial(...) (갔다 와서 곱하기 해야 함)
이번 코드: return factorialTail(...) (갔다 오면 끝임. 더 할 일 없음)
이제 factorialTail(5)는 다음 함수(factorialTail(4, 5))를 호출하고 즉시 스택에서 사라져도 됩니다.
어차피 자기가 더 계산할 게 없으니까요. 결과값만 그대로 전달하면 되거든요.
똑똑한 컴파일러는 이걸 알아채고, 새로운 스택 프레임을 만들지 않고 현재 프레임을 재사용(덮어쓰기)합니다. 이것이 꼬리 재귀 최적화(Tail Call Optimization, TCO)입니다.
TCO가 적용되면 10만 번 재귀를 돌아도 스택은 딱 1개만 씁니다. 사실상 while 루프와 똑같은 기계어 코드로 변환되기 때문입니다.
이론은 완벽한데, 현실은 시궁창입니다. 대부분의 언어와 엔진은 TCO를 지원하지 않습니다.
while로 바꿔주는 꼼수를 씀)결국 프론트엔드 개발자가 "내 코드는 꼬리 재귀니까 안전해!"라고 믿고 배포하면, 크롬 사용자는 에러를 뿜게 됩니다.
재밌는 점은, 함수형 언어를 표방하는 친구들은 TCO에 진심입니다.
@tailrec 어노테이션을 붙이면 컴파일러가 검사해 줍니다. 꼬리 재귀가 아니면 에러를 뱉습니다. (while로 변환됨)tailrec 키워드를 쓰면 됩니다. 역시 내부적으로 루프로 바뀝니다.gcc -O2 이상의 최적화 옵션을 켜면 기가 막히게 TCO를 해줍니다.하지만 우리의 주력인 Python, Java, JavaScript(V8)는 이걸 안 해줍니다. 그래서 "재귀가 우아하다"는 말은 이 동네에서는 통하지 않습니다.
언어가 안 해주면 우리가 직접 해야죠. 트램펄린이라는 기법이 있습니다. 재귀 함수가 결과를 바로 리턴하지 않고, "다음에 실행할 함수"를 리턴하게 만드는 겁니다.
// 트램펄린 함수: 함수를 받아서 계속 실행해줌
function trampoline(fn) {
let result = fn;
while (typeof result === 'function') {
result = result();
}
return result;
}
// 재귀 함수 본체
function factorialTrampoline(n, total = 1) {
if (n === 1) return total;
// 진짜 호출하는 게 아니라, "이거 호출해주세요"라고 함수를 던짐 (Thunk)
return () => factorialTrampoline(n - 1, n * total);
}
// 실행
trampoline(factorialTrampoline(10000)); // 스택 안 터짐!
이렇게 하면 깊이가 아무리 깊어져도 스택은 쌓이지 않습니다. 그저 while 루프가 돌고 있을 뿐이니까요.
CS 지식으로서 TCO는 정말 매력적이고 우아합니다.
하지만 실제, 특히 웹 개발 환경에서는 "그냥 for 문 쓰세요"가 정답입니다.
"우아한 코드는 기계가 이해하기 쉬운 코드가 아니라, 동료가 이해하기 쉬운 코드입니다."
Back when I was obsessed with functional programming, I tried to replace every loop with Recursion.
I thought for loops were relics of the imperative past, and recursion was the pinnacle of declarative elegance.
Then I ran a code calculating the factorial of 10,000. My browser crashed instantly.
RangeError: Maximum call stack size exceeded
My beautifully crafted code had turned into a memory-hogging monster.
"Why can loops run 100,000 times without breaking a sweat, but recursion crashes after a few thousand?" This question led me into the world of Tail Call Optimization (TCO).
Every time a recursive function is called, it leaves a trace in memory called a Stack Frame. This frame holds local variables, parameters, and the Return Address (where to go back to).
Let's look at a standard factorial function:
function factorial(n) {
if (n === 1) return 1;
return n * factorial(n - 1);
}
Here's how factorial(5) looks from the stack's perspective:
factorial(5)
┕ Waiting: 5 * ...
factorial(4)
┕ Waiting: 4 * ...
factorial(3)
...
factorial(5) cannot go home (pop off the stack) until factorial(4) finishes. Why? Because it still has work to do: the multiplication (5 * ?).
These functions pile up like a chain of sausages, occupying memory. When the depth gets too deep, the stack fills up and Overflows.
What if a function could say, "I have nothing left to do here, so just treat the next guy's result as my own" and then leave work early? This is the core concept of a Tail Call.
Let's rewrite the code:
function factorialTail(n, total = 1) {
if (n === 1) return total;
return factorialTail(n - 1, n * total); // Tail Position!
}
Do you see the difference?
return n * factorial(...) (Must multiply after return)return factorialTail(...) (Nothing left to do after return)Now, factorialTail(5) calls the next function (factorialTail(4, 5)) and can immediately disappear from the stack.
It has no pending calculations. It simply needs to pass the result along.
A smart compiler notices this and reuses the current stack frame (overwrites it) instead of creating a new one. This is Tail Call Optimization (TCO).
With TCO, you can run recursion 100,000 times, and it uses only 1 stack frame. Under the hood, it's compiled into the exact same machine code as a while loop.
The theory is perfect, but reality is messy. Most mainstream languages and engines do not support TCO.
while loops to support it).So if you, a frontend developer, deploy code thinking "It's tail recursive so it's safe!", millions of Chrome users will see your app crash.
Languages that embrace Functional Programming take TCO seriously.
@tailrec. The compiler guarantees TCO, or throws an error if your code isn't tail-recursive. (It compiles to a loop).tailrec keyword. Same deal.-O2) perform TCO aggressively.However, in our main territory (Python, Java, JavaScript/V8), we are out of luck. So the "Recursion is elegant" argument dies here. Without TCO, recursion is just a ticking time bomb.
When you encounter Maximum call stack size exceeded, your first instinct might be to increase the stack size limit (e.g. node --stack-size=1000).
Don't do this. It's a band-aid, not a cure.
Instead, use console.trace() to see where the recursion is spiraling.
function dangerousRecursion(n) {
if (n % 100 === 0) console.trace("Stack depth check");
dangerousRecursion(n + 1);
}
This will print the stack trace every 100 calls, letting you see exactly how deep you are before the crash.
Also, be wary of Accidental Non-Tail Calls.
// Looks like Tail Call, but isn't
return 1 + factorial(n - 1);
// Also not a Tail Call (Ternary operator nuance)
return n > 0 ? factorial(n - 1) : 0;
// (In JS this IS tail position, but some older compilers missed it)
You must ensure the return value is EXACTLY the function call, nothing else.
If the language won't optimize for us, we do it ourselves. There's a technique called Trampolining. Instead of returning a result, the recursive function returns a function representing the next step.
// Trampoline function: Takes a function and keeps executing it
function trampoline(fn) {
let result = fn;
// While the result is a function (a thunk), keep calling it
while (typeof result === 'function') {
result = result();
}
return result;
}
// Recursive function body
function factorialTrampoline(n, total = 1) {
if (n === 1) return total;
// Not a real call, but returning a function asking "Please call this next"
return () => factorialTrampoline(n - 1, n * total);
}
// Execution
trampoline(factorialTrampoline(10000)); // No Stack Overflow!
With this, no matter how deep the recursion logic is, the stack never grows. It's just a flat while loop spinning.