재귀함수가 스택 안 터지고 10만 번 도는 법 (Tail Call Optimization)

1. 프롤로그 - 재귀가 터진 날

함수형 프로그래밍에 심취했던 시절, 저는 모든 반복문을 재귀(Recursion)로 대체하려는 객기를 부렸습니다. for 문은 명령형(Imperative)의 시대착오적 유물처럼 보였고, 재귀야말로 선언형(Declarative)의 우아함이라고 믿었죠.

그러다 팩토리얼 10,000을 계산하는 코드를 돌렸을 때, 브라우저가 뻗어버렸습니다. RangeError: Maximum call stack size exceeded 아름답게 짰던 제 코드는 메모리 폭식 괴물이 되어 있었습니다.

"루프는 10만 번을 돌아도 멀쩡한데, 왜 재귀는 몇천 번만 돌아도 터지는 걸까?" 이 질문이 저를 꼬리 재귀 최적화(TCO)의 세계로 이끌었습니다.

2. 재귀가 비싼 이유 - 스택 프레임의 저주

재귀 함수는 호출될 때마다 메모리에 스택 프레임(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)합니다.

3. 해결책 - "바통만 넘기고 퇴근해라" (Tail Call)

만약 함수가 "나는 더 이상 할 일이 없으니, 다음 녀석이 한 일을 내 결과로 쳐라"라고 말하고 퇴근할 수 있다면 어떨까요? 이게 바로 꼬리 호출(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 루프와 똑같은 기계어 코드로 변환되기 때문입니다.

4. 현실 - 자바스크립트는 TCO를 해줄까?

이론은 완벽한데, 현실은 시궁창입니다. 대부분의 언어와 엔진은 TCO를 지원하지 않습니다.

Python: 귀도 반 로섬(창시자)이 "스택 트레이스 디버깅 힘들다"며 도입을 거부했습니다. (1,000번 넘으면 터짐)
Java: JVM 스펙상 지원 안 합니다. (Kotlin, Scala는 컴파일러가 while로 바꿔주는 꼼수를 씀)
JavaScript: ES6 스펙에는 TCO가 포함되었습니다! 하지만...
- Safari (WebKit): 유일하게 지원함.
- Chrome (V8): 지원 안 함. (구현했다가 버그+복잡성 때문에 롤백함)
- Firefox: 지원 안 함.

결국 프론트엔드 개발자가 "내 코드는 꼬리 재귀니까 안전해!"라고 믿고 배포하면, 크롬 사용자는 에러를 뿜게 됩니다.

4.5. 다른 언어는 어떨까? (Scala, Kotlin, C++)

재밌는 점은, 함수형 언어를 표방하는 친구들은 TCO에 진심입니다.

Scala: @tailrec 어노테이션을 붙이면 컴파일러가 검사해 줍니다. 꼬리 재귀가 아니면 에러를 뱉습니다. (while로 변환됨)
Kotlin: tailrec 키워드를 쓰면 됩니다. 역시 내부적으로 루프로 바뀝니다.
C++: 표준 스펙은 아니지만, gcc -O2 이상의 최적화 옵션을 켜면 기가 막히게 TCO를 해줍니다.

하지만 우리의 주력인 Python, Java, JavaScript(V8)는 이걸 안 해줍니다. 그래서 "재귀가 우아하다"는 말은 이 동네에서는 통하지 않습니다.

5. 대안 - 트램펄린(Trampoline) 기법

언어가 안 해주면 우리가 직접 해야죠. 트램펄린이라는 기법이 있습니다. 재귀 함수가 결과를 바로 리턴하지 않고, "다음에 실행할 함수"를 리턴하게 만드는 겁니다.

// 트램펄린 함수: 함수를 받아서 계속 실행해줌
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 루프가 돌고 있을 뿐이니까요.

6. 마무리 - 그냥 루프 쓰세요

CS 지식으로서 TCO는 정말 매력적이고 우아합니다. 하지만 실제, 특히 웹 개발 환경에서는 "그냥 for 문 쓰세요"가 정답입니다.

가독성이 더 좋고 (대부분의 개발자는 루프가 익숙합니다)
성능이 더 빠르고 (함수 호출 오버헤드가 없음)
브라우저 호환성 걱정이 없습니다.

"우아한 코드는 기계가 이해하기 쉬운 코드가 아니라, 동료가 이해하기 쉬운 코드입니다."

How to Run Recursion 100,000 Times Without Stack Overflow (Tail Call Optimization)

1. The Day My Recursion Exploded

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).

2. Why Recursion is Expensive: The Curse of Stack Frames

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.

3. The Solution: "Pass the Baton and Go Home" (Tail Call)

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?

Old Code: return n * factorial(...) (Must multiply after return)
New Code: 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.

4. Reality: Does JavaScript Support TCO?

The theory is perfect, but reality is messy. Most mainstream languages and engines do not support TCO.

Python: Guido van Rossum (the creator) explicitly rejected it, saying "It makes stack trace debugging too hard." (Recursion limit is usually 1,000).
Java: The JVM spec doesn't support it. (Languages like Kotlin/Scala compile tail recursion into while loops to support it).
JavaScript: The ES6 spec actually includes TCO! But...
- Safari (WebKit): The only one that supports it.
- Chrome (V8): No support. (They implemented it, then rolled it back due to bugs and complexity).
- Firefox: No support.

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.

4.5. What About Other Languages?

Languages that embrace Functional Programming take TCO seriously.

Scala: Use @tailrec. The compiler guarantees TCO, or throws an error if your code isn't tail-recursive. (It compiles to a loop).
Kotlin: Use the tailrec keyword. Same deal.
C++: Not in the standard, but compilers like GCC (with -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.

5. Debugging Stack Overflows

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.

6. Workaround: The Trampoline Technique

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.