Рекурсия с помощью Y–комбинатора

Y–комбинатор больше концептуальная вещь, которая позволяет больше узнать о внутренних свойствах рекурсии. Например, для огранизации рекурсии, нет необходимости знать имени функции, поэтому приведён пример для анонимной (лямбда) функции. Можно управлять выполнением рекурсии, см. Ycache и Y, при этом, не меняя содержания функции (некий аналог MVC — такое же разбиение по ответственности).

Рекурсия с помощью Y–комбинатора

Ещё один факт, который я забыл отметить: вторая форма фундаментально отличается тем, что в ней формально нет рекурсии, а в первой — она есть.
Вторая форма классическая, и является базой, на которой определяют примитивную рекурсию.

Рекурсия с помощью Y–комбинатора

Самое интересное в том, что сама функция вид не поменяла — в некотором роде, выполнено разделение между концептом и конкретными реализациями

Рекурсия с помощью Y–комбинатора

Здесь очень примерно происходит следующее:
Y(f)(x)=>(g(g))(x)=>[f(λ a: (k(k))(a))](x)=>
=>[f(λ a: (g(g)(g(g)))(a))](x)=>
=>[f(λ a: (f(λ a: (g(g)(g(g)))(a))))](x)
т.е. тоже получаем бесконечную развёртку.
^{(В скобках мог и намудрить)}