lambdas: y-combinator and z-combinator enable recursion

Lambda calculus doesn't have a way for an expression to refer to itself so we can't write recursive functions in the natural way we expect nowadays. The y-combinator (and it's lazy equivalent, the z-combinator) provide the plumbing to make it possible.

For example, naive factorial is naturally written recursively (note the recursive definition):

facR = n =>
  n < 1 ? 1 : n * facR(n-1)
                  ^^^^

The trick: if something could pass the fac function itself as an argument then it can recurse by calling that argument with itself and the next value:

fac' = facAgain =>
  n => n < 1 ? 1 : n * facAgain(facAgain)(n-1)
                       ^^^^^^^^^^^^^^^^^^
fac = fac'(fac')

The combinators generalise and externalise that plumbing so we can write:

fac' = recurse =>
  n => n < 1 ? 1 : n * recurse(n-1)
                       ^^^^^^^
fac = yCombinator(fac')

To do that, notice that facAgain(facAgain) needs to become a function argument recurse . Y combinator does that:

yComb = fn =>
  let wrappedFn = fnAgain => fn(fnAgain(fnAgain))
  in wrappedFn(wrappedFn)       ^^^^^^^^^^^^^^^^

The Z combinator does the same but makes that recurse function a thunk so that it doesn't overflow the stack in an eagerly evaluated language:

zComb = fn =>
  let wrappedFn = fnAgain => fn(n => fnAgain(fnAgain)(n))
  in wrappedFn(wrappedFn)       ^^^^                 ^^^