Tail-recursive traversal
Recursive algorithms whose recursive invocation is the final operation.
JS Puzzles · Const
Tail Call
A tail call is a final function call with no work left for the caller. Tail-call optimization can reduce stack usage for suitable recursion, but JavaScript engine support is not universal.
How it works
A tail call is a function call whose result is returned immediately, with no work left for the caller. In strict-mode code, an implementation can discard the caller's execution context before invoking the target, allowing tail recursion to avoid accumulating stack frames; this optimization is not consistently available in JavaScript engines.
Syntax
return functionCall(arguments);Key points
- A recursive call qualifies for tail-call optimization when it is the function's final operation and the caller has no remaining calculation.
- Because the caller has nothing left to do, the engine can avoid preserving its execution context for resumption.
- Reusing or discarding the caller's context reduces memory required by deeply recursive execution.
- Recursion depth is bounded by the particular JavaScript engine rather than by a universal language-wide number.
Common mistakes
- Do not assume that tail-recursive code is stack-safe: support varies by engine and the optimization has limited applicability.
- Even a recursive design that appears suitable for tail-call optimization may hit an engine-specific recursion limit.
Example: Tail-recursive factorial
"use strict";
function factorial(n, result = 1) {
if (n === 0) return result;
return factorial(n - 1, n * result);
}
console.log(factorial(5)); // 120The recursive call is the function's final operation, so it is in tail position. However, JavaScript engines do not all implement the optimization, so this pattern can still exhaust the call stack.
When to use it
Accumulator-based computation
Recursion with an accumulator carrying intermediate state.
Execution-stack analysis
Reasoning about stack growth in recursive JavaScript code.
Interview questions
QWhat is a tail call?
A tail call occurs when a function call is the final action of its caller, so the caller has no computation left afterward. A tail-recursive function passes its accumulated result into the recursive call rather than multiplying or adding after that call returns.
Follow-up: Why can ordinary recursive factorial overflow while a tail-recursive form may not? Ordinary recursion must retain each suspended caller for later work; a recognized tail call can avoid retaining those contexts, although engine support is uneven.
QWhat benefit does tail-call optimization provide, and is it guaranteed?
Tail-call optimization reduces memory pressure by avoiding storage of the caller's execution context when the recursive call is last. JavaScript engines do not universally provide this optimization, so code cannot depend on it for arbitrary input sizes.
Follow-up: What practical alternative avoids this portability issue? Rewrite the recursion as an explicit loop, which does not consume one JavaScript call frame per iteration.
QHow can you recognize whether a recursive call is in tail position?
In return factorial(n - 1, n * result), the recursive invocation is returned directly and no arithmetic follows it, making it tail position. In return n * factorial(n - 1), multiplication must happen after the recursive call returns, so that call is not tail position.
Follow-up: What must change to make the second form iterative? Carry the partial product in a variable and update it inside a loop before decrementing the counter.
Related
Recursionexecution contextexecution context stackrecursion depthtail call optimization