Tail Recursion
Every recursive function call adds a stack frame to the call stack. For deep recursion, this can exhaust available stack space and cause a stack overflow. Tail recursion is a specific recursive pattern that allows the runtime to reuse the current stack frame instead of adding a new one — eliminating stack overflow risk for deeply recursive algorithms.
Understanding tail recursion makes you a more precise programmer and helps you reason clearly about when recursion is safe versus when you need to convert to an iterative approach.
What Makes a Call "Tail Position"
A function call is in tail position if it is the very last action the function performs before returning. The caller does no additional computation after the call returns — it immediately returns whatever the callee returns.
// NOT tail recursive — multiplies n after the recursive call returns
function factorial(n) {
if (n <= 1) return 1;
return n * factorial(n - 1); // must wait for recursive result, then multiply
// ↑ this multiplication happens AFTER the recursive call
// n frames stay on the stack: factorial(5) waits for factorial(4) waits for ...
}
// IS tail recursive — recursive call is the FINAL action, nothing follows it
function factorialTail(n, acc = 1) {
if (n <= 1) return acc;
return factorialTail(n - 1, n * acc); // multiply BEFORE the call, pass as argument
// ↑ this IS the last action — no computation after it returns
}
// Trace for factorialTail(5):
// factorialTail(5, 1) → factorialTail(4, 5)
// factorialTail(4, 5) → factorialTail(3, 20)
// factorialTail(3, 20) → factorialTail(2, 60)
// factorialTail(2, 60) → factorialTail(1, 120)
// factorialTail(1, 120) → return 120Tail Call Optimization (TCO)
When a language runtime supports Tail Call Optimization (TCO), it detects tail-position calls and reuses the current stack frame rather than allocating a new one. This makes tail-recursive functions as memory-efficient as their iterative equivalents.
Without TCO: factorialTail(100000) → 100,000 stack frames → stack overflow With TCO: factorialTail(100000) → 1 stack frame (reused 100,000 times) → O(1) space
Converting to Tail Recursive Form
The key technique is to introduce an accumulator parameter that carries the partial result. Instead of computing after the recursive call, you compute before and pass the result as an argument.
// Pattern: add an accumulator parameter
// Non-tail: sum of 1..n
function sum(n) {
if (n <= 0) return 0;
return n + sum(n - 1); // adds n AFTER recursive call
}
// Tail recursive: acc carries the running total
function sumTail(n, acc = 0) {
if (n <= 0) return acc;
return sumTail(n - 1, acc + n); // adds to acc BEFORE calling
}
// Non-tail: reverse an array
function reverse(arr) {
if (arr.length <= 1) return arr;
return [...reverse(arr.slice(1)), arr[0]]; // concat AFTER recursive call
}
// Tail recursive: build result array via accumulator
function reverseTail(arr, acc = []) {
if (arr.length === 0) return acc;
return reverseTail(arr.slice(1), [arr[0], ...acc]); // prepend BEFORE calling
}
// Non-tail: flatten nested array
function flatten(arr) {
if (!Array.isArray(arr)) return [arr];
return arr.reduce((acc, item) => acc.concat(flatten(item)), []);
// This is NOT tail recursive — reduce calls flatten in non-tail position
}
// Tail recursive: use an explicit stack (worklist)
function flattenTail(arr, acc = [], stack = []) {
if (arr.length === 0 && stack.length === 0) return acc;
if (arr.length === 0) return flattenTail(stack.pop(), acc, stack);
const [head, ...tail] = arr;
if (Array.isArray(head)) return flattenTail(tail, acc, [...stack, head]);
return flattenTail(tail, [...acc, head], stack);
}JavaScript and TCO: The Harsh Reality
"use strict"; // TCO is spec'd for strict mode only
// This is technically tail recursive per the spec...
function factorialTail(n, acc = 1) {
if (n <= 1) return acc;
return factorialTail(n - 1, n * acc);
}
// ...but in Node.js / Chrome, this STILL causes stack overflow for large n:
// factorialTail(100000) → RangeError: Maximum call stack size exceeded
// The SAFE approach in JavaScript: always convert to iterative for deep recursion
function factorialIterative(n) {
let result = 1;
for (let i = 2; i <= n; i++) result *= i;
return result;
}
factorialIterative(100000); // works fine (result is Infinity due to JS number limits, but no overflow)The Trampoline Pattern
A trampoline is a higher-order function that simulates TCO in languages that do not support it natively. Instead of the recursive function calling itself, it returns a thunk (a zero-argument function). The trampoline runner keeps calling thunks until it gets a plain value.
// Trampoline runner — keeps calling the returned thunk until a value comes back
function trampoline(fn) {
return function(...args) {
let result = fn(...args);
while (typeof result === 'function') {
result = result();
}
return result;
};
}
// Tail-recursive factorial written as a thunk-returning function
function factorialThunk(n, acc = 1) {
if (n <= 1) return acc;
return () => factorialThunk(n - 1, n * acc); // return a thunk, don't call recursively
}
const factorial = trampoline(factorialThunk);
console.log(factorial(5)); // 120
console.log(factorial(10000)); // works! No stack overflow — loop in trampoline handles depth
// How it works:
// factorial(5)
// → factorialThunk(5, 1) returns () => factorialThunk(4, 5)
// → trampoline calls that thunk: factorialThunk(4, 5) returns () => factorialThunk(3, 20)
// → trampoline calls that thunk: factorialThunk(3, 20) returns () => factorialThunk(2, 60)
// → ... continues in a LOOP (no stack growth!) until factorialThunk(1, 120) returns 120Languages with Real TCO
Language | TCO Support | Notes |
|---|---|---|
Scheme/Racket | Guaranteed | Required by the spec; cornerstone of the language |
Haskell | Guaranteed | Lazy evaluation makes recursion idiomatic |
Erlang/Elixir | Guaranteed | Essential for long-running server processes |
Lua | Guaranteed | Tail calls are a first-class language feature |
Safari/JavaScriptCore | Implemented | Only JS engine with working TCO |
Python | None | Guido deliberately excluded it — "explicit is better than implicit" |
Java | None | JVM does not support it; use iteration |
Node.js / Chrome (V8) | Removed | Experimental implementation was removed |
When to Use Tail Recursion vs Iteration
In Scheme, Erlang, Elixir: tail recursion IS the idiomatic loop — always use it
In JavaScript/Python: prefer explicit iteration for anything that can be deep (n > 10,000)
In JavaScript/Python: tail recursion is still useful as a thinking tool to clarify logic
Use the trampoline pattern when you want recursive style but need to handle deep inputs
For tree/graph DFS, the recursion depth is O(height) — usually safe for balanced trees
Tail Recursion to Iterative Conversion
// Step 1: Original recursive factorial
function factorial(n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
// Step 2: Tail recursive with accumulator
function factorialTail(n, acc = 1) {
if (n <= 1) return acc;
return factorialTail(n - 1, n * acc);
}
// Step 3: Iterative — directly mirrors the tail recursive version
// The accumulator becomes a loop variable.
// The recursive call becomes a loop iteration.
function factorialIter(n) {
let acc = 1;
while (n > 1) {
acc = n * acc; // same as the acc parameter update
n = n - 1; // same as the n parameter update
}
return acc;
}
// This mechanical transformation always works for tail-recursive functions.
// Each parameter of the tail-recursive function becomes a variable in the loop.