Nothing in the pure lambda calculus can refer to itself by name, so how does recursion arise?
answer
- there is no name to call
- abstract over the recursive call
- a term that equals the step applied to itself
- fixed point of the one-layer body
- self-application supplies the copy
basics
~20 sThrough a fixed-point combinator. You write the body as a function whose first parameter stands for the recursive call, then apply a combinator that keeps handing that body another copy of itself, so the call site is supplied rather than named.
solid answer
~50 sAn abstraction is anonymous, so its body has no name to call. The move is to abstract over the recursive call itself: instead of a term mentioning its own name, write `F = λself. λn. ... self (...) ...`, which mentions nothing outside itself. What you want is a term `X` satisfying `X = F X` — a **fixed point** of `F`. A **fixed-point combinator** produces one. The classic is the **Y combinator**, `λf. (λx. f (x x)) (λx. f (x x))`: `Y F` and `F (Y F)` reduce to a common term, so every time the body reaches its recursive call it is handed another copy of itself. Self-application, the `x x`, is what supplies that copy without a name. Under a strategy that reduces arguments before applying, this particular term unfolds without end, so a variant that delays the copy behind an extra binder is used instead.
code
pseudocode · 9 linesF = λself. λn. IS_ZERO n THEN ONE ELSE MULT n (self (PRED n))
-- mentions no name of its own; `self` is just a parameter
Y = λf. (λx. f (x x)) (λx. f (x x))
Y F ==> (λx. F (x x)) (λx. F (x x))
==> F ((λx. F (x x)) (λx. F (x x)))
-- the argument F receives is the term Y F reduced to one step ago,
-- so `self` can unfold another layer whenever the body calls itgo deeper
Recall only the headline: an anonymous function has no name to call, and the way round it is to pass the function to itself as an argument. The formal machinery can wait.
Explain the two moves separately — abstracting over the recursive call to get a one-layer body, then obtaining a term equal to that body applied to itself. Say which of the two the combinator provides.
Show that termination is the body's responsibility, not the combinator's, and name the cost: every layer duplicates the self-applying term, and whether the copy is produced eagerly or on demand decides whether it unfolds at all.
The angle a lead owns is what a small core buys. Deriving recursion and data from two constructs makes a language cheap to specify and reason about, and pushes the entire cost onto whatever has to make the derived forms perform.
## Why a name is missing In the pure calculus there are no declarations. An abstraction `λx. B` is a value, not a definition, and it is never given a name that its own body could mention. So the shape every working programmer relies on — a function whose body calls the function being defined — has nothing to write at the call site. Recursion is not banned; there is simply no syntax for it. This matters beyond the puzzle. It is the reason a working engineer can say something precise about recursion: it is not a primitive that a language must provide, it is derivable from abstraction and application alone. Everything below is the derivation. ## Abstract over the recursive call The first move is the one that does the real work. Take the body you wanted to write and add a parameter standing for the recursive call: - Wanted, but unwritable: a term whose body calls *itself*. - Writable: `F = λself. λn. (if n is zero) 1 (else) n × (self (n − 1))`. `F` mentions no outside name. It is an ordinary two-parameter abstraction that happens to expect, as its first argument, the very function it is helping to define. Nothing recursive has happened yet — `F` is a *step*, a description of one layer. ## The fixed point, and the combinator that finds it What you now need is a term `X` such that `X` and `F X` are the same — a **fixed point** of `F`. If you had one, then `X` behaves like the recursive function: it is `F` applied to something that behaves like `X`, which is exactly what the recursive call needs. A **fixed-point combinator** is a term that produces such an `X` for any `F`. The famous one is the **Y combinator**: ``` Y = λf. (λx. f (x x)) (λx. f (x x)) ``` Its entire trick is **self-application**: `x x`, a term applied to itself. That is what makes a copy available without anything having a name. Reducing `Y F` substitutes `F` for `f` and then fires the application, producing `F` applied to the very same self-applying term. In other words `Y F` and `F (Y F)` reduce to a common term, and that is the fixed-point property stated precisely. The often-repeated shorthand "`Y F` reduces to `F (Y F)`" is close enough to convey the idea but is not literally a reduction in that direction; the two are interconvertible, which is all the property needs. ## Unfolding it once, by hand 1. `Y F` — substitute `F` for `f`, giving `(λx. F (x x)) (λx. F (x x))`. 2. Fire that application: `F ((λx. F (x x)) (λx. F (x x)))`. 3. The argument `F` just received is the term from step 1 — so `self` inside the body is bound to something that will unfold again on demand. 4. The body runs. If it reaches its base branch, it never touches `self` and the unfolding stops there. If it reaches the recursive call, step 2 happens again, one layer deeper. The termination question is therefore entirely the body's. The combinator supplies copies forever and guarantees nothing; a body with no branch that avoids `self` produces a term with no normal form, which is the formal counterpart of a runaway recursion. ## What it costs, and why languages give you names instead - **Each unfolding duplicates work.** The self-applying term is copied at every layer; nothing is shared, and nothing is memoised. - **It is sensitive to when arguments are reduced.** Under a strategy that reduces an argument before applying a function, this exact term unfolds forever regardless of the body, because the copy is produced eagerly. The usual fix is to wrap the copy behind an extra binder so it is only produced when the call site asks — the same term with one delay added. - **Any language with named definitions has the fixed point for free.** A name in scope inside its own definition *is* the self-reference, supplied by the language rather than constructed. The combinator is an existence proof, not a technique to reach for. - **It does have one practical descendant.** Where a function value is genuinely anonymous and still needs to call itself, the shape used is the same one: pass the function to itself as a parameter. That is the honest register for this material in an interview. Nobody is asked to write the combinator from memory. What is being checked is whether you know that recursion, like data, is derived here rather than assumed — and that the thing making it work is a function receiving a copy of itself as an argument.
- What stops the unfolding from continuing forever?Nothing in the combinator — the body does. Each unfolding hands the body one more copy of itself, so termination depends entirely on the body reaching a branch that never touches the parameter standing for the recursive call. A body with no such branch yields a term with no normal form, which is the formal version of a runaway recursion.
- Why is a fixed-point combinator a curiosity rather than a working technique?Because any language that lets you name a definition supplies the fixed point for free: the name inside the body refers to the definition being made. The combinator matters as an existence proof — recursion is derivable from abstraction and application rather than being a primitive — and as the shape used when a genuinely anonymous function still has to call itself.
saying these in an interview costs you the question
- Thinks recursion must be a primitive the calculus provides
- Says the combinator stores a pointer back to the function
- Claims the fixed point is found by searching candidate values
- Treats the combinator as a loop that iterates a counter
- Assumes the combinator terminates without a base branch in the body
- Cannot say what the body's extra first parameter stands for