No Let, No Rec, No Problem: A Gentler Introduction to the Y and Z Combinators

Let’s try to solve a simple enough puzzle in JavaScript: You have to write a function fact(n) which calculates the factorial of a number n , but you can not use loops ( for , while , etc), recursion, or even declarations ( let , const , etc).

We start with a canonical recursive non-solution to know what we're aiming for, in terms of behaviour:

function fact(n) { if (n === 0) { return 1 } else { return n * fact(n - 1) } }

This is a non-solution because we can not use recursion, which means we can not call the function fact from inside the definition of the function fact .

So, running for loops or calling fact from itself is not allowed. Then, what should we do? Can we call fact from some other function and try to arrive at the same behaviour?

After some thinking, we can write a function factf which calculates factorial but doesn't call itself:

function factf(n) { if (n === 0) { return 1 } else { return n * factg(n - 1) } } function factg(n) { if (n === 0) { return 1 } else { return n * factf(n - 1) } }

This works. factf(n) does calculate the factorial. So, are we done? Well, we did avoid explicit call for factf but it'd be a lie to say that this doesn't use recursion.

This solution calls for a new rule: mutual recursion is also NOT allowed.

... continue reading