Tail-Call Optimization: How Recursion Escapes the Stack Limit

Every recursive function you write is making a bet. The bet: the problem is small enough that the call stack won't overflow before you hit the base case. Most of the time, that bet pays off. Occasionally, it goes spectacularly wrong at 2am, and you're staring at a RecursionError: maximum recursion depth exceeded wondering why you ever thought Python was a reasonable choice for this.

Tail-call optimization (TCO) is the compiler trick that lets certain recursive functions run with O(1) stack space, as if they were loops. It surfaces in interviews in one specific, predictable way: the space complexity follow-up after you present a recursive solution. Knowing why it works, and which languages actually apply it, separates candidates who understand recursion from those who just use it.

What Is a Tail Call?

A tail call is a function call that is the last operation a function performs before returning. Not the last line. The last operation. The distinction matters more than it looks.

This is NOT a tail call:

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)  # multiplication happens AFTER the call returns

After factorial(n - 1) returns, the function still has to multiply the result by n. The current stack frame must survive that call to hold onto n. So it waits. Frame after frame waits. Like everyone in the queue to ask a "quick question" after a meeting.

This IS a tail call:

def factorial(n, acc=1):
    if n <= 1:
        return acc
    return factorial(n - 1, n * acc)  # nothing happens after this

The call to factorial(n - 1, n * acc) is the final act. The current frame has nothing left to do. It can be safely recycled before the next call even starts.

Why Stack Frames Exist at All

Each function call needs its own frame to hold the return address (where to jump back after the call finishes), local variables, and arguments. Without TCO, every active call keeps its frame alive until the call below it returns.

Walk through the non-tail-recursive factorial:

factorial(5)       <- frame alive, waiting
  factorial(4)     <- frame alive, waiting
    factorial(3)   <- frame alive, waiting
      factorial(2)
        factorial(1)  <- returns 1
      <- 1 * 2 = 2
    <- 2 * 3 = 6
  <- 6 * 4 = 24
<- 24 * 5 = 120

Five frames sitting in memory, holding onto their little n values like they'll need them for evidence. With tail recursion and a runtime that applies TCO:

factorial(5, 1)
  [reuse frame] factorial(4, 5)
  [reuse frame] factorial(3, 20)
  [reuse frame] factorial(2, 60)
  [reuse frame] factorial(1, 120)
  returns 120

One frame. The runtime updates the arguments and jumps to the top of the function. It is a loop, dressed in recursive syntax and pretending to be sophisticated.

O(1) Stack Space: What You're Actually Getting

This is the interview-relevant part. Without TCO, a tail-recursive function still costs O(n) stack space. With TCO, it costs O(1). The code is identical. What changes is whether the runtime bothers to apply the optimization.

Version	Time	Space
Non-tail-recursive	O(n)	O(n)
Tail-recursive, no TCO	O(n)	O(n)
Tail-recursive, with TCO	O(n)	O(1)

TCO never changes time complexity. It only collapses the stack. See recursion space complexity for why stack depth equals the longest active path, not the total number of calls.

Move the Work Forward, Not Backward

Converting a non-tail-recursive function to tail-recursive form usually requires an accumulator: an extra parameter that carries the work forward instead of deferring it to the return path.

The pattern is always the same. Find the operation happening after the recursive call returns, and fold it into the recursive call's arguments instead.

# Not tail-recursive: defers work on the way back up
def sum_list(lst):
    if not lst:
        return 0
    return lst[0] + sum_list(lst[1:])

# Tail-recursive: does all the work on the way down
def sum_list(lst, acc=0):
    if not lst:
        return acc
    return sum_list(lst[1:], acc + lst[0])

The accumulator absorbs computation as you descend. When you hit the base case, you return acc directly. No deferred arithmetic waiting in any frame above you. The call stack stops being a to-do list.

Which Languages Support Tail-Call Optimization

TCO is not just a compiler trick. It is a language-level decision, and languages have made very different choices about whether it is their problem to solve.

Language	TCO Support	Notes
Scheme / Racket	Required	Mandated by R5RS, R6RS, and R7RS standards
Haskell	Yes	Lazy evaluation makes it natural
Erlang / Elixir	Yes	Central to the actor model's infinite-loop idiom
Scala	Opt-in	@tailrec annotation; compile error if not actually tail-recursive
Kotlin	Opt-in	tailrec keyword; rewritten to a loop at compile time
C / C++	Compiler-dependent	GCC and Clang optimize tail calls at -O1 and above
JavaScript	Partial	Safari only; Chrome/V8 removed it after initial implementation
Java	No	JVM stack semantics rely on preserved frames
Python	No	Deliberate design decision
Ruby	No	MRI Ruby does not apply TCO

Python and JavaScript both said no. The reasons are worth knowing, because an interviewer asking about TCO might actually be asking whether you know why your language doesn't have it.

Why Python Deliberately Said No

Guido van Rossum wrote about this in a 2009 blog post. His argument: removing stack frames destroys tracebacks. When your Python program crashes, each level of the call stack tells a story. TCO would silently erase parts of that story, and suddenly your 40-line traceback becomes a cryptic one-liner that tells you nothing useful. Debugging becomes archaeology.

Python's position is that readable tracebacks are worth more than O(1) recursion space. The default limit sits at 1000 frames. If you are recursing deeper than that, Python is politely suggesting that you write a loop.

import sys
sys.setrecursionlimit(10000)  # buys headroom, not unlimited depth

This is not an oversight. Python chose debuggability over performance, as it does repeatedly and without apology. You can disagree with the call, but you should know it was a call.

Why JavaScript's TCO Story Is Complicated

ES6 (2015) formally included proper tail calls in the ECMAScript specification. V8 implemented it experimentally under the name "STC" (Syntactic Tail Calls). Then they removed it. The reason: JavaScript debuggers rely on call stacks for meaningful error messages, profiling, and performance traces. TCO silently eliminates frames, making Error.stack unreliable and DevTools confusing in ways that affect every JavaScript developer's daily life.

Safari's JavaScriptCore still implements ES6 TCO. Chrome and Node.js do not. If you write tail-recursive JavaScript today, assume you have no TCO guarantee unless you know your runtime is Safari. The spec says one thing. The most popular runtimes do another. Welcome to JavaScript.

Kotlin and Scala Did This Right

Both languages found a middle path: opt-in with compiler verification.

tailrec fun factorial(n: Long, acc: Long = 1L): Long {
    if (n <= 1L) return acc
    return factorial(n - 1L, n * acc)
}

The tailrec modifier tells the Kotlin compiler to rewrite the function as a loop. If the function is not actually tail-recursive, you get a compile-time error instead of silent O(n) behavior. The output bytecode is a while loop. No frames, no nonsense, no guessing.

import scala.annotation.tailrec

@tailrec
def factorial(n: Int, acc: Int = 1): Int =
  if n <= 1 then acc
  else factorial(n - 1, n * acc)

The @tailrec annotation in Scala works identically. It is a verification tool. If the call is not in tail position, the compiler refuses to compile it. You get the optimization you asked for, and you know you got it.

Both approaches beat the alternative: writing tail-recursive code, assuming the runtime will optimize it, and discovering at n=50,000 that it doesn't.

How This Comes Up in Interviews

You will rarely be asked to implement TCO directly. It surfaces in three concrete ways.

The space complexity follow-up. You present a recursive solution. The interviewer asks: "What is the space complexity?" You say O(n) for the call stack. They follow up: "Is there a way to get O(1) space recursively?" The answer is tail recursion, if the language supports TCO. In Python or Java, the honest answer is: you need to convert to iteration. See convert recursion to iteration for the mechanics of that.

Language-specific accuracy. If you write a tail-recursive solution in Python and claim O(1) space, you are wrong. Python will not give you that optimization, and saying otherwise signals that you don't fully understand how the language executes your code. That is a rough thing to signal in an interview about code execution.

Senior and staff-level design rounds. Trade-off discussions sometimes probe language and runtime choices. Knowing why Python rejected TCO, or why V8 removed it after ES6 mandated it, is exactly the kind of engineering judgment that higher-level interviews are trying to surface.

When to Just Write a Loop

If you need O(1) space in a language without TCO, the pragmatic answer is iteration. Any tail-recursive function can be mechanically converted to a loop, because that is exactly what a TCO runtime does internally. You are just doing the compiler's job yourself, which is a fine thing to do.

# Tail-recursive (still O(n) space in Python, Guido said so)
def factorial(n, acc=1):
    if n <= 1:
        return acc
    return factorial(n - 1, n * acc)

# Iterative equivalent (actually O(1) space)
def factorial(n):
    acc = 1
    while n > 1:
        acc *= n
        n -= 1
    return acc

The iterative version is exactly what a TCO runtime produces internally. Writing it yourself makes the optimization explicit instead of depending on a runtime that may or may not bother. In Python, it is not even a choice.

If you want to practice stating these trade-offs out loud the way a real interview requires, SpaceComplexity runs voice-based mock interviews with rubric-based feedback, including on the space complexity questions that trip up the most candidates.

Further Reading

• Wikipedia: Tail call
• Kotlin tailrec documentation
• ECMAScript specification: Tail position calls
• Scala @tailrec annotation docs
• MDN: Call stack