Learning path

Full curriculum

Full curriculum

Arrows go from each prerequisite to the units that depend on it. Hover or focus a unit to highlight its path.

Unit content

Tail calls and proper tail recursion

A function call is in tail position when its result becomes the result of the current function without any further computation.

In

function f(x):
    return g(x)

the call to g is a tail call. In

return 1 + g(x)

it is not, because the caller must resume to perform the addition.

A runtime with proper tail calls can reuse the current continuation or stack frame for a tail call instead of growing the call stack.

This makes tail-recursive loops execute in bounded stack space. For example,

function sum(n, acc):
    if n == 0: return acc
    return sum(n - 1, acc + n)

needs no pending computation after its recursive call, so a proper-tail-call implementation can run it with constant call-stack growth.

Tail-call optimization is not merely “making recursion fast.” It follows from a semantic observation: once a computation enters a tail call, the caller has nothing left to do. Languages that guarantee proper tail calls therefore permit iteration and state-machine style control to be expressed through function calls without imposing linear stack growth.