The Y combinator - understanding recursion without recursion

Recursion is central to functional programming, as a clearer alternative to loops as other control structures typical of imperative languages. Functional programming encourages programmers to study recursion in greater depths. I first encountered the Y combinator in the mind-bending penultimate chapter of the wonderful The Little Schemer, which explores recursion in great depth. In an effort to unbend my own mind on the subject, I decided to derive it for myself, so I could see how it worked, and gain an extra tool in dealing with recursion and closures.

Do you now know why Y works? Read this chapter just one more time and you will – The Little Schemer

The Y combinator was discovered by Haskell Curry in the 1940s. It allows recursion to be captured without functions needing to reference themselves by name. It provides some insight into the nature of recursion in the lambda calculus (where nothing has a name), and also demonstrates the power of closures.

We will conduct our explorations mostly in scheme, because it's expressive, concise and elegant, but we also give examples in Haskell and JavaScript at the end. The Haskell version is ludicrously simple and clear (relying on lazy evaluation), while the JavaScript version mirrors the Scheme version.

The Y combinator allows the programmer to pass in a function which isn't explicitly recursive (doesn't reference itself by name), but describes a step in a recursive process with a continuation, and provides back a new function which recursively applies that step using itself as the continuation.

Let's start by making the term "step in a recursive process with a continuation" more concrete, and clarify how the Y combinator acts on these steps.

To give us something specific to think about, let's examine the factorial function. The classic recursive definition of factorial is expressed in Scheme as follows

(define (factorial n)
  (if (= n 0)
    1
    (* n (factorial (- n 1)))))

This definition references itself. We can view it as an equation in terms of factorial, however. In fact, we can define

(define (factorialize f)
  (lambda (n)
    (if (= n 0)
      1
      (* n (f (- n 1))))))

and observe that (factorialize factorial) (factorialize applied to the factorial function) is itself factorial. The formal way to say this is that factorial is a fixed-point of factorialize.

Its important to understand that factorialize operates on all functions from numbers to numbers. In terms of function, we can look at factorialize as doing a single step in the factorial function, and then, instead of recursing, handing off the remainder of the work to a continuation which is passed in as a parameter. This is what is meant by a "step in a recursive process with a continuation". factorialize itself is not recursive - it hands the recursion over to some continuation which is passed in.

The Y combinator turns these recursive steps into full-blown recursive functions. Applied to factorialize it finds a fixed point (you can prove by induction that such a fixed point is necessarily the factorial function). This means we can define the factorial function by

(define factorial
  (Y factorialize))

where here, Y is the Y combinator. How does it do this? In effect it passes factorialize in as the continuation to factorialize, so that the same recursive step is applied over-and-over, until we reach the base case.

We started with the factorial function, so that ought to work as expected:

(define factorial
  (Y
   (lambda (recur)
     (lambda (n)
       (if (= n 0)
           1
           (* n (recur (- n 1))))))))


(factorial 5)

;Value: 120

Another easy example is defining the length of a list:

(define length
  (Y
   (lambda (recur)
     (lambda (l)
       (if (null? l)
           0
           (+ 1 (recur (cdr l))))))))


(length '(1 2 3))

;Value: 3

Multiple calls to recur also work just fine:

(define fibonacci
  (Y
   (lambda (recur)
     (lambda (n)
       (cond
        ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (recur (- n 1))
                 (recur (- n 2)))))))))


(map fibonacci (list 0 1 2 3 4 5 6 7 8))

;Value: (0 1 1 2 3 5 8 13 21)

We can also use the Y combinator's definition to write recursive lambdas inline. To give a contrived example using length of lists:

(map
  ((lambda (F)
     ((lambda (f) (f f))
      (lambda (recur)
        (F (lambda (x) ((recur recur) x))))))
   (lambda (recur)
     (lambda (l)
       (if (null? l)
           0
           (+ 1 (recur (cdr l)))))))

  '((1) (1 2) (1 2 3)))

;Value: (1 2 3)

Let's try and get a different intuition for how Y works. Let's lean on our factorial and factorialize example some more.

One intuitive way to get factorial out of factorialize, is to pass factorialize something like factorialize as it's argument. In fact, each of the following gets closer and closer to factorial

(factorialize factorialize)                                ; Evaluates correctly for 0
(factorialize (factorialize factorialize))                 ; Evaluates correctly for 0, 1
(factorialize (factorialize (factorialize factorialize)))  ; Evaluates for correctly 0, 1, 2
...

One can think of factorial as being something like

(factorialize (factorialize (factorialize ...)))

Notice that to evaluate factorial on a given number, we only need finitely many of these calls to factorialize.

In fact, if we expand, for example, ((Y factorialize 3)) we get

(factorialize
  (factorialize
    (factorialize
      ((factorialize _) 0))))

where the _ represents a lambda which is never evaluated.

The Y combinator is not restricted to Lisps. Let's give examples of the Y combinator in Haskell and JavaScript.

y :: (a -> a) -> a
y f = let g = f g in g

factorial :: Integer -> Integer
factorial = y factorialize
  where
    factorialize _ 0 = 1
    factorialize recur n = n * recur (n - 1)

const y = (f) => ((g) => g(g))(
    (recur) => f((x) => recur(recur)(x))
);

const factorialize = (recur) => (n) => n == 0 ? 1 : n * recur (n - 1);
const factorial = y(factorialize);

Lambdas really are way more powerful than you would at first think! I found understanding how to derive the Y combinator gives me a new way to think. There really are good reasons why functional programming reveres the lambda so much - they are the Jedi weapon par excellence.

I can imagine many folks would balk at the code for the y combinator - it's hard to see what it does at a glance. It's nonetheless wonderfully abstract, and can be understood by its properties. Nonetheless, explicit recursion is probably clearer.