# Deriving Y Combinator

## Deriving Y Combinator that makes recursive functions without assignments possible.

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.

Let us just print the returned value

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?

Oops, this does not work because the recursive call is using `fact` which is no longer defined

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).

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.

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

Note the above code does NOT need assignment operator (and `const factorial =` is only there for clarity). We might as well write the expression

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

We can also move the nested series of calls `step(step(...` from the end and pass it as argument to `step(fact)`.

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)`.

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.

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.

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

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

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.

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`.

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

to this

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.

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

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

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!

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!