# Cryptic Recursion

Original:

After abstraction:

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.