Continuation-Passing Style: Make the Remaining Work Explicit

To compute 3!, a recursive factorial leaves “multiply by 3” waiting while it computes 2!. Step to the base case, then switch between Direct and CPS to see the same pending multiplications represented in two ways.

def fact_cps(n, k):    if n == 0:        return k(1)    def after_child(v):        return k(n * v)    return fact_cps(n - 1, after_child)fact_cps(3, lambda v: v)

What is a continuation?

A continuation is the computation that remains after an expression produces a value. In 3 * fact(2), the continuation of fact(2) includes multiplying its result by 3 and delivering that answer to the caller. It describes what happens to the value, rather than the calculation that produces it. The Scheme Programming Language, section 3.3

In direct style, ordinary calls and returns carry this information implicitly. Continuation-passing style, or CPS, passes the remaining computation explicitly as a function, conventionally named k. Instead of returning its answer for the caller to process, a CPS function calls k with that answer. The Scheme Programming Language, section 3.4

The explorer assumes small nonnegative integers and the definition 0! = 1. Its steps are an authored model of the calculation, not an execution trace from Python. Switching styles preserves the arithmetic milestone; the pending-work count excludes the final identity continuation, labeled Finish.

Turn the waiting work into a function

The direct-style expression n * fact(n - 1) has two stages: compute the child result, then multiply by n. The CPS version puts the second stage inside after_child and passes that function to the child.

This is a complete runnable Python example for nonnegative integer inputs:

def fact(n):
    if n == 0:
        return 1
    return n * fact(n - 1)


def fact_cps(n, k):
    if n == 0:
        return k(1)

    def after_child(v):
        return k(n * v)

    return fact_cps(n - 1, after_child)


answer = fact_cps(3, lambda v: v)
assert answer == fact(3) == 6

Each after_child is a closure: it retains the n and k belonging to the particular invocation that created it. When the child supplies v, the closure multiplies n * v and passes the product to the older continuation. The earlier work remains reachable through that captured k. Python’s rules for nested function scope

There are three important changes in the code:

1. The function receives an extra argument, k, describing how to use its result.
2. The base case calls k(1), so it follows the same protocol as the recursive case.
3. The recursive call receives after_child, which combines this invocation’s multiplication with its existing continuation.

The initial lambda v: v is the identity continuation. It gives the final answer back unchanged. Calling fact_cps(3, lambda v: v + 10) instead produces 16: the outer computation now adds 10 after all the factorial multiplications.

The displayed return statements are Python’s way to forward the result of the next call. The continuation argument expresses the intended control flow; spelling a call with return does not make Python eliminate its caller.

Read the chain in the right order

For 3!, descent creates three functions. The explorer names them by creation order:

The base case receives K3. Passing it 1 starts the chain K3 → K2 → K1 → Finish: multiply by 1 to get 1, by 2 to get 2, and by 3 to get 6. Creation order and invocation order are reversed because each newer function receives the result before forwarding it to the older one.

Direct style performs those same three multiplications while returning through its waiting callers. CPS makes their order and connections visible as function values. No multiplication has disappeared.

Tail position does not settle the memory question

The recursive fact_cps call is in tail position: its result is forwarded directly. The call to k is also in tail position; its multiplication happens before that call. A runtime with proper tail calls can transfer control without retaining a redundant return chain. The R6RS rationale explains this through continuation semantics: a tail-called procedure uses the same continuation as its caller. R6RS rationale, proper tail recursion

That guarantee concerns the call path. The factorial transformation still constructs one multiplier closure for each positive n. At the base case, the newest closure links to all the older ones, retaining O(n) continuation records in this straightforward representation. A compiler may optimize their representation; CPS alone promises neither that optimization nor constant total memory. This count also leaves aside the space occupied by growing integer values.

In CPython, the example above still grows Python call depth. During descent, recursive fact_cps calls accumulate; during continuation invocation, ordinary calls to the closures also accumulate until the final value returns. CPython does not implement tail-call optimization for Python functions, including in its optional tail-call interpreter. Deep inputs can therefore hit the recursion limit. Python 3.14 release notes, Python recursion-limit documentation

The explorer intentionally counts unfinished multiplier functions, not live closures or Python frames. A completed multiplication can stop appearing as pending work while a real Python activation and its references remain alive. To track actual allocation or stack behavior, an execution must be instrumented separately.

What explicit control makes possible

Passing the next computation as a value lets a program choose where to send a result. For example, separate success and failure continuations can describe different next steps. A compiler can use CPS as an intermediate representation that makes control transfers explicit. TSPL’s success and failure continuations, GNU Guile’s CPS intermediate language

CPS does not, by itself, schedule asynchronous work: the Python example calls every continuation immediately. It also does not capture the current execution context automatically. Scheme’s call/cc provides that capture operation; the functions above are constructed explicitly by the program. TSPL’s continuation capture operation

This leaves a practical question: how can Python execute an explicit chain without recursively calling the next function? A trampoline makes each step return a description of the next call to a loop. CPS describes what should happen next; the trampoline supplies a stack-safe way to run those steps. An interpreter’s dispatch mechanism addresses another transfer boundary, the connection between instruction handlers.

Related concepts