Tail Call Optimization
Subject: Computer and Technology noun /ˈteɪl kɔːl ˌɑːp.tɪ.məˈzeɪ.ʃən/ 1 definition
- compiler-optimization
- programming-languages
- functional-programming
- memory-management
-
Definition (noun)
Entry #88 · UpdatedTail Call Optimization (TCO) is a compiler and runtime technique that executes a subroutine call in the tail position—where the caller returns the callee's result directly with no remaining computation or cleanup—without allocating a new stack frame. Instead of pushing a new return address and local frame onto the call stack, the generated code reuses or replaces the caller's existing frame and transfers control via an unconditional jump so the callee returns straight to the original caller. This keeps stack usage constant across arbitrarily deep chains of tail calls, allowing recursive algorithms and state machines to run without stack overflow errors when supported by the language's calling convention and runtime semantics.
Common Forms
Self-Tail Recursion Elimination: Rewrites a function whose final operation is calling itself into an iterative loop by updating parameter bindings in place and branching back to the function's entry point.
Sibling Call Optimization: Replaces a tail call to a different function with a direct jump after popping or reusing the current stack frame, applied by native compilers such as GCC and LLVM when calling conventions align.
Proper Tail-Call Semantics: Enforces unbounded stack-frame reuse across arbitrary and mutually recursive tail calls at the language or virtual-machine specification level, as guaranteed in Scheme, Lua, and Erlang.
Trampoline Emulation: Achieves constant stack depth in runtimes without native tail-call support—such as the JVM or CPython—by returning deferred call thunks to an outer loop that invokes them sequentially.
Example
An Erlang telemetry broker runs a long-lived worker process that handles 500,000 sensor events per minute by ending its message-handler function with a recursive tail call passing the updated session map. Because the BEAM virtual machine applies tail call optimization, each iteration reuses the existing stack frame rather than pushing a new one, allowing the process to run indefinitely in constant stack memory without overflowing.