At the end of The Little Schemer, the authors lead you step-by-step through the process of deriving the Y Combinator. They do this repeatedly abstracting a `length`

function–and then magically, the Y Combinator appears. It is a pretty neat trick, and certainly mind-bending on your first read through the book.

Since Javascript has first-class functions, we can derive the Y Combinator in Javascript as well. I will take a different approach than *The Little Schemer*. This approach owes a lot to a couple of blog posts I read on the subject^{1}.

Since this is a post about recursive functions, then we can use that old chesnut, `factorial`

. Here is a possible implementation of `factorial`

in Javascript:

Let’s start by making a non-recursive `basicFactorial`

, which we’ll call `nonRecursive`

:

All we’ve done here is replace the recursive call of `basicFactorial`

. Instead, we pass in a function that will get called. We can pass any function that returns something that supports the `*`

operator:

But it starts to get a little interesting when we pass `basicFactorial`

in there. Then we get back … `basicFactorial`

!

In other words, `basicFactorial`

is a fixed point of the function `nonRecursive`

.

This is pointless in this case, since we have defined `basicFactorial`

already. But suppose we had not defined `basicFactorial`

. Wouldn’t it be nice if there was a function that we could pass `nonRecursive`

to that would return the fixed point of it, i.e. the `factorial`

function?

That is what the Y Combinator does. Pass `nonRecursive`

to `Y`

, and out comes the factorial function:

Note that:

Or in other words:

So if we have `Y`

, we do not need to define `basicFactorial`

*at all*, we let `Y`

derive it from the non-recursive function `nonRecursive`

. Now let’s look at it from the other direction, and build up to `Y`

. Here again, is the functional `nonRecursive`

that we want to calculate the fixed point of:

As noted above, pass `basicFactorial`

in, and `nonRecursive`

returns `basicFactorial`

. Notice that we have pretty much defined factorial in the body of `nonRecursive`

: `return n === 0 ? 1 : n * f(n-1);`

–why not use that? So here’s our next try: Apply `nonRecursive`

to itself. This requires a small change to the body of `nonRecursive`

, to self-apply the passed-in function to get the body out and apply it to the inner argument.

Now we want to isolate the fixed point function. Let’s wrap that in a function `g`

:

Since inner function `g`

does not depend on anything in closure, we can pull it out:

The pulled-out function may look familiar–it’s `nonRecursive`

again. Here’s what’s left over after `g`

(a.k.a. `nonRecursive`

) is pulled out; let’s call it `almostY`

:

We’ve pulled `g`

out of `almostY`

, but `almostY`

still depends on `g`

. The final step is to wrap `almostY`

in a function that takes the functional `g`

as an argument. Then `almostY`

will have no dependencies.

So, let’s wrap it in a function that takes our non-recursive factorial functional and returns the fixed point of it. And since this is the last step, let’s call that function `Y`

:

Holy crap! It works! But it’s not just for factorial–`Y`

will provide a fixed point for any unary function, e.g.

As presented, this version of `Y`

can only handle unary functions, and it will blow up the stack for relatively low values of `n`

. It is straightforward to extend `Y`

to handle functions of any arity, and to memoize it.

- I found these articles helpful: Fixed-point combinators in JavaScript: Memoizing recursive functions and Deriving the Y combinator.