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
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 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
fact = Y H, so voila, we know
fact. End of story.
fact = Y \f.\n.((= n 0) 1 (* n (f (- n 1))))