Functional programming in JavaScript (3)

Functional programming is also about recursion. Take a simple factorial:

const fac = n => n > 1 ? n * fac(n-1) : 1

console.log( fac(5) );

That looks super easy but what if you want to write a recursive function without using a recursive function name in its definition?

In the above example, this would mean you can bind a function to a variable fac but you can't use the name fac in the function definition.

Not possible?

Consider this, then:

const fac = 
  (f => n => n > 1 ? n * f(f)(n-1) : 1)
  (f => n => n > 1 ? n * f(f)(n-1) : 1);

console.log( fac(5) );

which technically means that you don't even need to bind it to a separate name (fac):

console.log(
  (f => n => n > 1 ? n * f(f)(n-1) : 1)
  (f => n => n > 1 ? n * f(f)(n-1) : 1)
  (5)
)

Hold on, most of us need time to comprehend this. Let's examine.

The core definition of the function:

n => n > 1 ? n * fac(n-1) : 1

just got a new level of abstraction:

f => n => n > 1 ? n * f(n-1) : 1

but to actually be able to piggyback the function onto itself, we need to pass it to itself as f and in the same time, pass the passed function to itself in every call, f(f):

  (f => n => n > 1 ? n * f(f)(n-1) : 1)
  (f => n => n > 1 ? n * f(f)(n-1) : 1)

This is clever and one could ask: what if I don't want to repeat the definition twice so that I can pass it to itself?

This is doable but with an auxiliary helper called the Y combinator.

Consider this:

const Y = f => (x => f(y => x(x)(y)))(x => f(y => x(x)(y)));

const fac = Y(f => n => n > 1 ? n * f(n-1) : 1);

This auxiliary helper function, called Y, basically wraps this passing-a-function-to-itself. Note that its core body

x => f(y => x(x)(y))

is indeed repeated twice. This higher order function, Y, is now a factory of functions and can make any function recursive, the recursive call is resolved not by-name but by-binding: in our example, Y is applied to:

f => n => n > 1 ? n * f(n-1) : 1

and note that f binds the supposed recursive function name here.

And, because this core body is repeated twice, Y can be refactored to:

const Y = f => (x => x(x))(x => f(y => x(x)(y)));

const fac = Y(f => n => n > 1 ? n * f(n-1) : 1);

And that's it. The Y is undeniably an impressive idea.