# Anonymous recursion & the Y Combinator

Normally, recursion requires us to have a name that is *bound* to the function which is recursive, e.g. we need a name "fact" to be *bound* to the factorial function itself in order for us to be able (i.e., recursively) use the name "fact" within the definition of the factorial function.

However - e.g. in lambda calculus, due to functions having no essential difference from data/objects e.g. literal number "42" - functions can be anonymous.

If you're reading this, you've probably read that a thing called the "Y Combinator " can help us with this task (viz. creating an anonymous recursive function, where "anonymous" means "does not have a name bound to it").

**This article explains "what the Y Combinator does", and "how to use it" (but not "what it is" or "why and how it works" etc.).**

Pseudo-spoiler: the Y Combinator is: `Y = \f.(\x.(f (x x)) \x.(f (x x)))`

(well, this doesn't really answer the above questions... so not a real spoiler.)

We want to define a "fact" like this:

```
fact = \n.((= n 0)
1
(* n
(fact (- n 1)))
```

However, we don't want the word (or say, *name*) `fact`

to appear in the, "expression" if you like (i.e. this thing on the right-hand side of the equals sign), of the definition of the "fact" function itself. We can move it out a bit using the reversed process of a *beta reduction*:

```
fact = \f.\n.((= n 0)
1
(* n
(f (- n 1)))) fact
```

Allow me to give *that* (you know what I'm pointing at!) chunk of stuff a name "H":

```
fact = H fact
```

Good! `H`

applied to `fact`

is, again, `fact`

. Clearly and intuitively, `fact`

is a "fixed point" of the function H. And how do we know how to express `H`

explicitly? - Well, we've already done that!

Now the question lies in: How do we find the "fixed point"(in this case, "fact") of a given function (in this case, "H")?

The answer is easy - use `Y`

!

`Y`

is the "fixed point operator". It returns the fixed point for any function provided to it. We don't know or care about how the mysterious `Y`

is expressed (well, we sort of do...), but by its definition, or "purpose" if you like, we know:

```
fact = Y H
```

(If you substitue around, you'll see that:

```
Y H = fact = H fact = H (Y H)
Y H = H (Y H) = H (H (Y H)) = H (H (H (H (...))))
```

Well, just thought the above two lines was worth pointing out.)

Now, we know `H`

, know `fact = Y H`

, so voila, we know `fact`

. End of story.

```
fact = Y
\f.\n.((= n 0)
1
(* n
(f (- n 1))))
```