Y combinator

The Y combinator or Y constructor is a formula in lambda calculus which allows the definition of recursive functions in that formalism.

Church invented the Y combinator:

Y = (\h . (\x. h (x x)) (\x. h (x x)))

which has the cute property that it reproduces whatever argument we give it:

   Y A   ===> A (Y A)
         ===> A (A (Y A))
         ===> A (A (A (Y A)))
         ===> A (A (A (A (Y A))))
         ===> ...