Commissioned for this museum · after Haskell Curry's fixed-point combinator

Recursion Without a Name

JavaScript·1969·8 lines·331 bytes

// The Y combinator: recursion for a language that has none.
//
// Nothing below names itself. `fact` never says "fact", and yet it recurs.
const Y = (f) => ((x) => x(x))((x) => f((...args) => x(x)(...args)));

const fact = Y((recur) => (n) => (n <= 1 ? 1 : n * recur(n - 1)));

console.log([1, 2, 3, 4, 5, 6].map(fact).join(" "));

Curator’s note

Look at the factorial and notice what is missing. It never mentions its own name. fact is the name the *outside* uses; inside, the function that computes factorial refers to recur, which is handed to it. Recursion here is not a language feature being used — it is a thing being built, out of nothing but functions taking functions.

The engine is (x) => x(x), self-application: a function given itself as its own argument. That single move is where the loop comes from, and it is also why writing Y naively hangs. x(x) in a language that evaluates arguments before calls would expand forever, so the inner (...args) => x(x)(...args) wraps the self-application in another function — delaying it until someone actually calls with arguments. That wrapper is not decoration. Remove it and this file never prints anything.

Why anyone cared: the lambda calculus has no way to name a function, and yet computation clearly requires repetition. Curry's combinator settles it — recursion is not something a language must provide, it is something that falls out of functions alone. Everything Turing-complete gets it for free whether it meant to or not.

Read it once more with that in mind and the seventy characters of Y stop looking like a puzzle and start looking like a proof. It is also, more prosaically, the reason your language's let rec is a convenience rather than a necessity.