Cryptic Recursion

 

Original:

((function(f){return f(f);})(
    (function(make_factorial){
        return function(n){
            return (n===0) ? 1 : n * make_factorial(make_factorial)(n-1);
        };
    })))(5);

After abstraction:

const op = (x,y) => x*y;    //similar to op in accumulate(op, init, xs)
function gen(n){
    return t => op(n,t);    //op constructor
}
(f=>f(f))(func => 
                n => n === 0 
                        ? 1 //base case
                        : gen(n)    //do something at this layer
                          (func(func)(n - 1)))    //wishful thinking
          //previous two lines are like op(n, accumulate(the_rest))
(5);

In the program above, gen(n) is used to generate an operator function using function op. An operator function is a function that receives the second operand and outputs the result of op(n, _the_second_operand).

I believe the most cryptic part is why func(func)(n-1) is written that way. Why does func appear twice and why not func(func(n-1))? First, func should be a function thet receives and outputs a function, because it is a parameter of function f => f(f). Then, we consider why func is used twice:

Let g(x) be the equivalent of our target function, which means g(x) is equal to the factorial of x. Let f(x) be the function defined by func => ..., which means f(x) = the result of the expression where we replace all func on the LHS of => with the value of x. In the program below, x * something part is dealt with by gen(n), so I’ll simply write x * something there for easier reading.

g(n) = f(f)(n)
     = f(n => n * g(n - 1))
     = f(n => n * f(f)(n - 1))

g(n-1) is replaced with f(f)(n-1) because we know that g(n) = f(f)(n) and we can replace all n with x-1. Okie Dokie, QED.

Other words

I guess func(f)(n) means t => n * f(t-1) in this case, so func(func)(n) is actually doing the recursive step. By substitution, we obtain func(func)(n) = t => n * func(t-1), which displays the “call itself” property of a recursive process.

Confusion

In Source, expression const f = (t => t === 0 ? 1 : f(t-1)); is legal. It is strangely similar to the substituttion of func(func)(n). However, Prof. Henz explicitly warned that const a = a + 1; is illegal even if we have const a defined in an outer context (cause if it is in the same context, const a would be redefined, if it is not in the outer context, a on the RHS would be undefined). I am afraid that the behavior of func(func)(n) is similar to the “illegal” behavior of such a const assignment.