Y combinator

A special case of a combinator is the fixed point combinator, known as the Y combinator or Y constructor, also sometimes known as "fix". The Y combinator has the property that:

Y x = x (Y x)

The Y combinator can be used to implement recursion. The Y combinator is a formula in lambda calculus which allows the definition of recursive functions in that formalism. See the lambda calculus article for a detailed explanation.

Somewhat surprisingly, the Y combinator can be defined as the non-recursive lambda abstraction:

Y = λ h . (λ x . h (x x)) (λ x . h (x x))