Why use the Y combinator for recursion?

Question

The Y combinator is defined as $$Y=\lambda f.(\lambda x. f (x x))(\lambda x. f (x x))$$ It has the following useful property: $$Y g = g (Y g)$$ for some expression $g$. It can be easily used to implement a recursive function, e.g. factorial:

Y = lambda f : (lambda x : f(lambda v : x(x)(v)))(lambda x : f(lambda v : x(x)(v)))
F = lambda r : lambda n : 1 if n == 0 else n * r(n - 1)
fact = Y(F) # same as F(Y(F)), therefore the r in the body becomes Y(F) which is fact
print(fact(5))

The above code outputs 120, as expected. (The Y combinator in the code differs from the one at the start of the question. This is because the one at the start would cause a recursion depth exception. They are equivalent in the lambda calculus nonetheless)

---

An alternative method, which is the topic of my question, is as follows:

F = lambda r : lambda n : 1 if n == 0 else n * r(r)(n - 1)
fact = F(F) # r gets substituted with F, therefore the expression in the body becomes F(F) which is fact
print(fact(5))

This once again outputs 120, but is more readable and straightforward in my opinion.

---

If the second method works, then what is the point of using the Y combinator? Wikipedia says this about the second method:

…The self-application achieves replication here, passing the function's lambda expression on to the next invocation as an argument value, making it available to be referenced and called there.

This solves it but requires re-writing each recursive call as self-application. We would like to have a generic solution, without a need for any re-writes:…

It then proposes the first method as a better solution. What do they mean by generic solution?

Answer 1

One way of thinking about why $Y$ would be preferable is that it separates 'content' from 'plumbing'. Typical notation for recursive definitions in practical languages is something like:

$$\mathsf{fact} = λn. \mathsf{if}\ n = 0\ \mathsf{then}\ 1\ \mathsf{else}\ n * \mathsf{fact} (n-1)$$

It is desirable to just be able to factor out the body with minimal changes, like:

$$λ \mathsf{fact}\ n. \mathsf{if}\ n = 0\ \mathsf{then}\ 1\ \mathsf{else}\ n * \mathsf{fact} (n-1)$$

We get this simply by adding an argument with the same name as the desired recursive definition; there's no need to change the body. So, it is purely (as can be) the 'content' that distinguishes your recursive definition. Then $Y$ takes care of the 'plumbing' necessary to make $\mathsf{fact}$ actually work like a recursive call and so on.

Your alternate definition has moved some of the plumbing into the content function, by inlining the part where $\mathsf{fact}$ is passed a copy of itself. This replaces $Y$ with the simpler $λf. f f$, but it complicates the content with some of the details of how the looping is being achieved. These details would need to be copied into every content function.

So, $Y$ is preferable in the sense that it confines the implementation details of looping into one function, so that the 'bodies' of recursive definitions can be written in the straight forward way.