Deriving the Y Combinator in 7 Easy Steps.

Here is an easy to remember definition of Y in Scheme:

(define (Y f)
    (f (lambda (x) ((Y f) x))))

An anonymous recursive function that computes the factorial of 10 with the help of Y:

((Y (lambda (f)
  (lambda (n)
(if (= n 0)
    1
    (* n (f (sub1 n)))))))

  10)

=> 3628800

As you can see the combinator is bound to the identifier Y. But if we can bind a function to an identifier, why we need Y in the first place?. We don’t. We need Y when the language don’t allow binding functions to names and as a consequence do not have a convenient way to make recursive calls. Assuming that our implementation of Scheme is very primitive and do not provide these conveniences, we can define the factorial function as:

(((lambda (f)
  (f (lambda (x) ((Y f) x)))) ;; The Y combinator.

    (lambda (f)
      (lambda (n)
        (if (= n 0)
        1
        (* n (f (sub1 n)))))))

  10)

=> 3628800