# 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

- the function

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