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.