# Y combinator

``````λf.(λx.f(x x)) (λx.f(x x))
``````
• The y combinator is a way to implement recursion in lambda calculus
• Most basic recursion representation:
``````loop = loop
``````
• Consider representing “loop” in lambda calculus (the “omega combinator”):
``````(λx.x x) (λx.x x)
``````
• the function `λx.x x` takes an input `x` and returns `x` as output
• we apply this function to itself
• this concept of “self application” is the key to recursion

simple example:

``````   (λx.x x) (λx.x x)
; expanded:
=> (λ(λx.x x).(λx.x x) (λx.x x)) (λx.x x)
; result:
=> (λx.x x) (λx.x x)
``````

general example:

``````rec f = f(rec f)
= f(f(f( ...
``````

a definition of “rec” in lambda calculus (y combinator):

``````λf.(λx.f(x x)) (λx.f(x x))
``````
• note that the y combinator includes the same sort of “self application” or “omega combinator” included in “loop”, though the y combinator is not itself recursive because it relies on the “f” input, which is the function that should be recursed
• as the “omega combinator” is applied to itself, expanded, and evaluated, it naturally calls the “f” function input each time it’s evaluated, allowing for recursion