This is how one can start with factorial function and avoid using assignment operator by deriving and using Y Combinator function. This is based on the excellent and mind bending presentation by Jim Weirich at ScotlandJS. I highly recommend watching the video. This blog post only summarizes the code snippets I was writing as I was following along.

I am skipping the prerequisites and start at the recursive factorial problem, approximately at minute 26 of the video.

Let us start with recursive factorial and compute factorial of 5 to make sure it works.

1 | const fact = n => n === 0 ? 1 : n * fact(n - 1) |

Let us just print the returned value

1 | console.log((() => { |

Great. But why do we need the intermediate assignment `const fact = ...`

inside?
All it does is wait for `fact(5)`

call, which we can do right away, right?

1 | console.log((() => |

Oops, this does not work because the recursive call is using `fact`

which is no longer defined

1 | console.log((() => |

So we need to somehow make a recursive call to itself inside the unnamed function. Hmm. That is the crux of the matter: can we write recursive functions without named functions (using just function expressions) and without assignment operator? Everything should be just an expression: a function applied to its arguments.

First attempt: let us deal with small values of `n`

. In fact, let us deal with the simplest
case - a factorial of `0`

. In that case, the recursive call would never happen we can literally
pass *anything* just to make sure variable `fact`

is defined (but it will never be used).

1 | console.log((() => { |

See how we pass string `foo`

as `fact`

, but it was never used and so everything was ok?

Whatever the value we passed as argument `fact`

to function `step`

better know how to
compute factorial of `n - 1`

whenever we are computing the factorial of `n`

. Let us say we want
factorial of `1`

. What function should we pass to `step`

that knows how to compute factorial of
`0`

? Hint: we just saw it above - it is `factorial(0)`

, aka `step('foo')`

!!! Just pass
it to itself, and we then call the returned result function to compute factorial of 1.

1 | console.log((() => { |

And if we want to compute factorial of 5 (or 4 or 3 or 2) we should keep nesting `step(step(...`

calls.

1 | console.log((() => { |

Note the above code does NOT need assignment operator (and `const factorial =`

is only there
for clarity). We might as well write the expression

1 | console.log((() => { |

Ok, this is nice, but does not really scale to larger numbers. We somehow need to avoid manually creating this nested call chain and instead create it on demand.

Observation: if the very first argument to nested `step(step(...`

calls does NOT matter (and we
even have used `foo`

string instead of the function), we can just pass `step`

itself as first
value

1 | console.log((() => { |

We can also *move* the nested series of calls `step(step(...`

from the end and pass it as argument
to `step(fact)`

.

1 | console.log((() => { |

Interesting. We are passing `function step(fact){...}`

as argument `s`

to this weird function,
which in turn just calls it multiple times! The result of calling it multiple times goes back
into `step(fact)`

as `fact`

argument. Kind of a "I will call you, you will call me" circle.

Hmm, so many nested `s(s(s(s(...`

calls! All we need really is to call `s(s)`

in order to
*teach* the algorithm how to recursively call itself. Let us remove almost *all* calls, except
for one `s(s)`

.

1 | console.log((() => { |

Hmm, we are missing something - and that something is the fact that `fact(n)`

no longer is so
simple. Instead it needs to call *itself* again in order to call `s(s)`

again, which will call
`step(fact)`

, and so on, until the recursion stops at `n === 0`

check. The only difference
on the code below from the code above is the recursive call: `fact`

was replaced with `fact(fact)`

expression.

1 | console.log((() => { |

Now we have a recursive expression without using assignment operator which can compute factorial of any number. We can refactor the above code for clarity because we want to be able to write recursive functions easily.

Start with renaming `s`

and `fact`

arguments `gen`

because it is the same.

1 | console.log((() => { |

I don't like calling `gen(gen)`

inside the "simple" factorial function `step`

, so we should try
getting rid of it. We can start by moving the `n`

argument *up* into its own wrapper function

1 | console.log((() => { |

Ok, still works. Now let us create *another* function around the simple factorial without any
arguments for a moment.

1 | console.log((() => { |

And now let us supply arguments to these two inner functions. The outer one - we can
pass `gen(gen)`

, which is what we wanted to do anyway.

1 | console.log((() => { |

And for the inner function, the simple factorial, we can do the same, but for clarity I will
rename the argument from `n`

(which stays outside) to `k`

.

1 | console.log((() => { |

The inner part looks like a curried function with two applications though, so we can refactor from this

1 | function (n) { |

to this

1 | function (n) { |

But even better would be to extract this anonymous function cleanly, because this is the essence of recursive factorial algorithm; all the other code around it is just our extra machinery to avoid using the assignment operator. Literally, rip the above factorial and pass it as an argument! I will call the argument "algo" to make it clear.

1 | console.log((() => { |

The code might be a little better written if we separate calling it and printing the result.

1 | const F = function (algo) { |

Finally, separating the of the algorithm code, we can write generic "Y combinator" function that can make any function recursive without using assignment operator

1 | // Y combinator function |

Interesting observation: the `function factorial`

is very forgiving to what `partial`

can be.
For example, you can pass the computed `Y(factorial)`

back to `factorial`

and get the same result!

1 | console.log('factorial(Y(factorial))(5) =', factorial(Y(factorial))(5)) |

This is because all `factorial`

expects from `partial`

is the ability to correctly compute
factorials of smaller values.

Also, interesting to note that the computed value `F = Y(factorial)`

can be passed back
to `factorial(F)`

and we get it back again: `factorial(Y(factorial)) = Y(factorial)`

.
In math, this special value is called the `fixed point`

of a function: `f(x) = x`

. In our
case `f`

is `function factorial`

and `x`

is `Y(factorial)`

.
So the Y combinator computes the fixed point of a given function!

## Links

A few alternative derivations in JavaScript

- The Y Combinator explained with JavaScript
- I strongly recommend reading JavaScript Allongé because it is awesome.