The Y Combinator

The problem: recursion with no name

To write a recursive function the obvious way, you give it a name and let the body refer back to that name. Factorial calls factorial; the definition mentions the very thing it is defining. That looks innocent, but it smuggles in a language feature: the ability of a binding to see itself. In the pure untyped lambda calculus — the minimal model where everything is an anonymous one-argument function and the only operation is applying one to another — there is no let, no global names, and no def. A lambda has no name, so it has nothing to call.

So how do you recurse? You hand the function a copy of itself as an argument. Write the body so its first parameter is "the function to call for the recursive case," then arrange for that parameter to be bound to the whole function. The Y combinator is the device that performs that arrangement automatically, for any function, using nothing but application. Feed Y a non-recursive "template" — a function that describes one layer of the recursion and takes "myself" as a parameter — and Y returns a fully recursive function. It is the trick that proves recursion is not a primitive: it falls out of plain function application.

Concretely, you write factorial in open form, where self is the recursion you don't yet have:

F = λself. λn. if n == 0 then 1 else n * self(n - 1)

F is not recursive — it never mentions F. It just expects someone to pass it the real recursive function as self. Y F is exactly that someone: it ties the knot so self ends up bound to Y F itself.

Why it's called a "fixed-point" combinator

A fixed point of a function f is a value p with f(p) = p — applying f changes nothing. The Y combinator's whole job is captured by one equation:

Y f = f (Y f)

That says Y f is a fixed point of f: feeding Y f back into f returns Y f again. Now look at what that means for our factorial template. The fixed point of F is the function fact such that F(fact) = fact — and F(fact) is "factorial, given that fact is the recursive call." The fixed point of "one layer of factorial" is factorial. Y manufactures that fixed point for any template you give it.

The classic untyped definition (Curry's Y) is:

Y = λf. (λx. f (x x)) (λx. f (x x))

The engine is the term λx. f (x x) — call it g. Y applies g to itself: g g. Watch one beta-reduction:

Y f
  = (λx. f (x x)) (λx. f (x x))     -- this is g g
  = f ((λx. f (x x)) (λx. f (x x))) -- substitute g for x in the body f (x x)
  = f (Y f)                          -- the inner term is g g = Y f again

That last line is the fixed-point property, derived purely by substitution. The x x — a function applied to itself — is the self-replication that re-creates the recursion on demand, one layer per call. No name was ever used.

Step-by-step: factorial unfolding

Trace (Y F) 3 under lazy evaluation. Each expansion exposes exactly one f, i.e. one copy of the body, and binds self to "do it again":

(Y F) 3
  = F (Y F) 3                       -- by Y F = F (Y F)
  = (λn. if n==0 then 1 else n * (Y F)(n-1)) 3
  = 3 * (Y F) 2
  = 3 * (F (Y F) 2)
  = 3 * (2 * (Y F) 1)
  = 3 * (2 * (1 * (Y F) 0))
  = 3 * (2 * (1 * (F (Y F) 0)))
  = 3 * (2 * (1 * 1))               -- base case: n==0 returns 1
  = 6

The combinator only ever unrolls as far as the recursion demands — it is not an infinite object, it is a lazy stream of "selves" produced one beta-step at a time. The cost is real, though: each recursive call performs the self-application g g again, so a Y-based factorial does roughly the same number of reductions as named recursion plus a constant factor of two to three for the combinator plumbing per level. There is no asymptotic penalty — O(n) calls for n! stays O(n) — but a constant-factor slowdown of about 2–3× versus a directly named function is typical because every level re-evaluates the wrapper.

The catch in strict languages

The pretty derivation above assumed lazy (normal-order) evaluation, where arguments are only evaluated when needed. JavaScript, Python, OCaml and most mainstream languages are strict (applicative-order, call-by-value): they fully evaluate an argument before passing it. Under that rule, the inner x x in Y gets reduced before f is ever applied, which triggers another x x, which triggers another — the program diverges before it computes anything. Paste the literal Y into Python and you get a stack overflow, not a factorial.

The fix is the Z combinator, which eta-expands the self-application so it is wrapped in a lambda and therefore only forced when actually applied to a real argument:

Z = λf. (λx. f (λv. x x v)) (λx. f (λv. x x v))

The change is tiny — x x becomes λv. x x v. Because a lambda is a value, the strict evaluator stops there instead of charging ahead into infinite self-application. The wrapped term unfolds one more level only when the next argument arrives, which is precisely when the recursion needs it. Same fixed point, same answer; the Z combinator is simply the call-by-value-safe Y, and it is what you actually write in JavaScript or Python.

Y combinator vs other ways to recurse

	Y combinator	Z combinator	Named recursion	U combinator (self-pass)	Built-in fix
Definition	λf.(λx.f(x x))(λx.f(x x))	λf.(λx.f(λv.x x v))(λx.f(λv.x x v))	let rec / def	λg.g g	language primitive
Needs a name?	No	No	Yes	No (caller passes self)	No
Works under call-by-value?	No (diverges)	Yes	Yes	Yes (if you eta-wrap)	Yes
Simply-typeable?	No	No	Yes	No	Yes (built in)
Runtime overhead	~2–3× constant	~2–3× constant	baseline	~2× constant	baseline
Typical use	theory, teaching	strict-language demos	all production code	stepping stone to Y	Haskell, Scheme, proof assistants

The honest takeaway: in any language with let rec or a built-in fix, you should use those. The Y combinator earns its place because it shows recursion is not a feature you must build into the language — it emerges from function application alone. That is a result about the foundations of computation, not a coding recommendation.

What the numbers and history actually say

• Curry, 1940s. Haskell Curry formalized fixed-point combinators within combinatory logic; the untyped lambda calculus they live in was introduced by Alonzo Church in the 1930s, the same calculus he used to prove the Entscheidungsproblem undecidable in 1936.
• Every lambda term has a fixed point. This is a theorem, not a coincidence: for any f, the term Y f reduces to f (Y f). This is the fixed-point theorem of the lambda calculus; Kleene later carried the same idea into computability theory as his recursion theorems.
• Constant-factor cost, not asymptotic. A Y/Z-based factorial does the same O(n) work as a named one, with roughly 2–3× more allocations/reductions per level for the combinator wrappers. The big-O class is identical.
• Infinitely many fixed-point combinators exist. They all satisfy the same equation F n = n (F n). A famous example is Klop's combinator Y_k = L L L L L L L L L L L L L L L L L L L L L L L L L L — a single term L applied to itself 26 times, where L is chosen so the 26 bound variables spell out "this is a fixed point combinator." Curry's Y is just the smallest well-known one.

JavaScript implementation

JavaScript is strict, so we implement the Z combinator. The literal Y would loop forever:

// Z combinator — the call-by-value-safe Y. Recursion with no name.
const Z = f => (x => f(v => x(x)(v)))
               (x => f(v => x(x)(v)));

// Open (non-recursive) factorial: `self` is the recursion we don't have yet.
const factStep = self => n => (n === 0 ? 1 : n * self(n - 1));

const factorial = Z(factStep);
console.log(factorial(5)); // 120 — and `factStep` never names itself

// Fibonacci, same recipe:
const fibStep = self => n => (n < 2 ? n : self(n - 1) + self(n - 2));
const fib = Z(fibStep);
console.log(fib(10)); // 55

Two things to notice. First, factStep takes self as its first argument and uses it for the recursive call — that extra parameter is the seam where Z plugs the function back into itself. Second, the eta-wrap v => x(x)(v) is load-bearing: drop the v and write x(x) and you are back to the diverging Y. The wrapper defers the self-application until a real argument shows up.

Python implementation

# Z combinator in Python (also strict / call-by-value).
Z = lambda f: (lambda x: f(lambda v: x(x)(v))) \
              (lambda x: f(lambda v: x(x)(v)))

# Open factorial: `self` is supplied by Z.
fact_step = lambda self: lambda n: 1 if n == 0 else n * self(n - 1)

factorial = Z(fact_step)
print(factorial(5))   # 120

# Open Fibonacci.
fib_step = lambda self: lambda n: n if n < 2 else self(n - 1) + self(n - 2)
fib = Z(fib_step)
print(fib(10))        # 55

For comparison, the literal Y below is mathematically correct but will raise RecursionError the instant you call it in Python, because the argument x(x) is evaluated eagerly:

# DO NOT call — diverges under strict evaluation. Shown only to contrast with Z.
Y = lambda f: (lambda x: f(x(x)))(lambda x: f(x(x)))
# Y(fact_step)(5)  -> RecursionError: maximum recursion depth exceeded

The only difference between the working Z and the broken Y is the lambda v: ... v wrapper — a one-line illustration of why evaluation order is the whole story for fixed-point combinators.

Variants worth knowing

The U combinator. U = λf. f f applies a function to itself. It is the pedagogical first step: if you manually write a function that expects to receive itself and call U on it, you get recursion without Y. Y is essentially U with the boilerplate factored out so the user's function doesn't have to do the self-passing.

The Z combinator. Covered above — the applicative-order fix that real strict languages need.

The Θ (Turing) combinator. Alan Turing's fixed-point combinator, Θ = (λx.λy. y (x x y)) (λx.λy. y (x x y)). Unlike Y it reduces to f (Θ f) in a single step without the substitution trick, and it is sometimes preferred in proofs for that cleaner reduction behavior.

Polyvariadic fixed-point combinators. Generalizations that take a tuple of mutually-recursive functions and return their simultaneous fixed point — the combinator behind desugaring a set of mutually recursive let rec bindings (e.g. isEven/isOdd) into pure lambda calculus.

Recursive-type Y. To make Y type-check, wrap the self-applied argument in a recursive (μ) type so x : μa. a -> b has a roll/unroll pair. This is how typed languages without a built-in fix (and how the metatheory of System F + μ-types) recover the combinator.

Common bugs and edge cases

• Pasting the literal Y into a strict language. The single most common mistake — Y = λf.(λx.f (x x))(λx.f (x x)) stack-overflows in JS/Python/OCaml. Use Z (the λv. x x v wrap).
• Forgetting the self parameter. Your function must be in open form — self => n => ... — and call self, not its own name, for the recursive case. If you write a normally-recursive function and pass it to Z, the combinator does nothing useful.
• Dropping the eta-wrap. In Z, writing x(x) instead of v => x(x)(v) reintroduces eager divergence. It must stay a lambda.
• Expecting it to type-check. In TypeScript, Haskell, or OCaml the self-application x x produces an "occurs check" / infinite-type error unless you introduce a recursive type. The untyped form lives only in dynamically-typed or explicitly-untyped settings.
• Confusing the fixed point of f with a fixed point of a number. The fixed point here is a function — the recursive routine itself — not a numeric value where f(p) = p for some integer.
• Assuming no overhead. Y/Z preserve big-O but add a 2–3× constant factor and extra allocations per call. For hot paths, named recursion or an iterative loop wins.