Recursion and Fixed-Point Combinators

We have booleans, numbers, pairs and conditionals — but every recursive definition we might write, like factorial, seems to need a name to call itself, and the lambda calculus has no names, no let rec, no global definitions. A function is anonymous; how can something with no name refer to itself? The answer is a single, almost magical term — a fixed-point combinator — that manufactures recursion out of self-application. It is the last piece that makes three tiny rules Turing-complete, and understanding it is the intellectual summit of the untyped lambda calculus.

The problem: a function that needs itself

Suppose we want factorial. Informally, \text{fact}\ n = \text{if}\ n=0\ \text{then}\ 1\ \text{else}\ n \times \text{fact}(n-1). The body mentions \text{fact}, the very thing we are defining. In the lambda calculus we cannot write that directly. But we can abstract the recursive call away, turning the self-reference into an ordinary parameter f:

F \;=\; \lambda f.\, \lambda n.\, \text{IF}\ (\text{ISZERO}\ n)\ \overline{1}\ \big(\text{MULT}\ n\ (f\ (\text{PRED}\ n))\big)

Here F is a perfectly ordinary closed term — no self-reference. It takes a function f (to be used for the recursive call) and returns "one level" of factorial. What we actually want is a term \text{FACT} that, when passed to F as its own f, reproduces itself: \text{FACT} = F\ \text{FACT}. That is, \text{FACT} must be a fixed point of F.

Fixed points, and why every term has one

A fixed point of F is a term X with F\ X =_\beta X. In ordinary mathematics not every function has a fixed point; in the lambda calculus, astonishingly, every term does — and a single combinator produces it.

The proof is the reduction itself. Let W = \lambda x.\, F\,(x\, x). Then Y\ F \to W\ W = (\lambda x.\, F\,(x\, x))\ W \to F\,(W\, W). But W\, W is what Y\ F reduced to, so Y\ F =_\beta F\,(W\, W) =_\beta F\,(Y\ F). The self-application x\, x — legal only because the calculus is untyped — is the engine: it feeds a function a copy of itself.

The unrolling

Because Y\ F =_\beta F\,(Y\ F), applying Y to F and reducing exposes copies of F one at a time — an infinite potential unrolling that stops only when the conditional inside F chooses the base case. Step through the first turns of the crank:

Each \to_\beta step peels off one more g. When g is our factorial builder F, one peel is one recursive call: the term grows a new layer exactly when \text{IF}\ (\text{ISZERO}\ n) takes the else branch, and stops unrolling when n reaches 0 and the base value \overline{1} is returned. Recursion is a fixed point being lazily unrolled on demand.

Y diverges under call-by-value: the Z combinator

There is a catch. In a call-by-value setting (most real languages, and the JavaScript our code compiles to), Y\ F loops forever before it can do any useful work: CBV insists on reducing W\, W to a value, and W\, W \to F\,(W\, W) keeps regenerating W\, W as an argument to be evaluated first — divergence. The cure is to η-expand the recursive occurrence, wrapping it in a \lambda so it is passed as a suspended function rather than an eagerly-evaluated value. That is the Z combinator (Rosser's applicative-order fixed point):

Z \;=\; \lambda f.\, \big(\lambda x.\, f\,(\lambda v.\, x\, x\, v)\big)\,\big(\lambda x.\, f\,(\lambda v.\, x\, x\, v)\big)

The inner \lambda v.\, x\, x\, v is x\, x η-expanded: it delays the self-application until an argument v actually arrives, so CBV stops unrolling until the recursive call is really made. Under normal order, Y and Z behave identically; under call-by-value, Z is the one that works.

Recursion from nothing, running

Below, the Z combinator is written verbatim in TypeScript — no function name recurses, no loop appears. We pass Z a non-recursive "one level" builder for factorial and for Fibonacci, and genuine recursion emerges. Press Run.

// The Z combinator (call-by-value fixed point), exactly as the maths above. // Z = λf. (λx. f (λv. x x v)) (λx. f (λv. x x v)) const Z = (f: any) => ((x: any) => f((v: any) => x(x)(v)))((x: any) => f((v: any) => x(x)(v))); // A NON-recursive "one level" of factorial: `self` is the recursive call, handed in by Z. const factStep = (self: any) => (n: number): number => n === 0 ? 1 : n * self(n - 1); const fact = Z(factStep); // Z ties the knot — no named recursion anywhere console.log("factorial via Z:"); for (let n = 0; n <= 6; n++) console.log(` ${n}! =`, fact(n)); // Fibonacci the same way. const fibStep = (self: any) => (n: number): number => n < 2 ? n : self(n - 1) + self(n - 2); const fib = Z(fibStep); console.log("fibonacci via Z:"); console.log(" fib(10) =", fib(10)); // 55 // The fixed-point equation, checked: Z F and F (Z F) agree on inputs. console.log("fixed point? Z F (4) === F (Z F) (4):", fact(4) === factStep(Z(factStep))(4)); // true — Z F = F (Z F)

Not one const fact = function fact(...) in sight, yet fact(6) is 720. The recursion lives entirely in the self-application inside Z. The final line checks the defining equation Z\ F = F\,(Z\ F) numerically — the fixed-point theorem, made to compute.

The Y combinator looks like a cheat: it produces a fixed point without knowing anything about F, and the equation Y\ F = F\,(Y\ F) is circular-looking. The magic dissolves once you see that the "circle" only unwinds as far as the computation demands. Each application of the recursive function forces exactly one more copy of F to appear, and the conditional inside F is the brake: when the argument hits the base case, the else-branch (with its recursive call) is never selected, no further copy of F is demanded, and the unrolling halts. So Y supplies a bottomless well of self-copies, and F's own logic decides how deep to draw. Terminating recursion is a fixed point whose unrolling is stopped by a base case; non-terminating recursion — a missing or unreachable base case — is simply Y handed a term that never stops asking for the next copy, i.e. \Omega in disguise.

The elegant Y = \lambda f.\, (\lambda x.\, f\,(x\, x))\,(\lambda x.\, f\,(x\, x)) will stack-overflow instantly if you transcribe it literally into JavaScript, OCaml or any call-by-value language. The reason is precisely the evaluation-order lesson: CBV evaluates the argument x\, x to a value before the call, and x\, x regenerates itself endlessly, so the recursion unrolls to infinite depth with no computation. This is not a bug in Y — under normal order it is perfect — but a strategy mismatch. The fix is the Z combinator, whose extra \lambda v η-guards the self-application so it fires only when an argument arrives. Rule of thumb: normal-order world → use Y; call-by-value world → use Z.

A conceptual caution too: Y\ F being a fixed point does not mean Y "computes" F's result. Y only ties the knot; all the actual work — multiplying, decrementing, testing for zero — is done by F itself. The combinator supplies self-reference and nothing more.