Can you create recursion using only anonymous functions?

A secret lesson in the history of computer science

Here’s a thought experiment. Let’s say you want to write a recursive function. But, for some crazy reason, you can’t give this function a name. Can you do it?

To help us visualize the problem, let’s start with a JavaScript example of normal (though pointless) recursion.

function myRecursiveFunction() {
  myRecursiveFunction();
}
myRecursiveFunction();

Can we eliminate this function’s need to know its own name? Well yeah, you say, we can just pass in the function to recurse on. If we think about it for a second, there’s nothing inherently special about recursive calls. You’re just calling a function, which could even be a function that’s passed in.

function myRecursiveFunction(functionToCall) {
  functionToCall(functionToCall);
}
myRecursiveFunction(myRecursiveFunction);

Cool, but now we’re stumped. Surely this function needs a name so that you can pass it as an argument to itself. But hold on, what if you create some generic thing that takes a function and calls it with itself? Maybe this can be useful. Let’s call this thing a combinator.

function combinator(func) {
  func(func);
}

Or, anonymously:

(func) => func(func)

Which we can then call with our function to recurse on.

function myRecursiveFunction(functionToCall) {
  functionToCall(functionToCall);
}
((func) => func(func))(myRecursiveFunction);

And we’re almost there! Since the recursive function is only referenced as an argument to the combinator, let’s move it there. This will help us strip it of its name in the next step.

((func) => func(func))(
  function myRecursiveFunction(functionToCall) {
    functionToCall(functionToCall);
  }
);

Finally:

((func) => func(func))(
  (functionToCall) => functionToCall(functionToCall)
);

Or, just to make this particularly hard to decipher, you can even write it as:

((f) => f(f))((f) => f(f));

And there you go! Copy that little snippet into your JavaScript console and you’ll see that it causes a stack-overflow. All in a purely functional, non-procedural way. How exciting!

But can this technique be used to create something less trivial? Sure, why not? Here’s a slightly more complicated example. This calculates 100! (100 factorial) by recursively multiplying every number from 1 to 100.

((func, x) => func(func, x))(
  (func, x) => (
    x <= 1
      ? 1
      : x * func(func, x - 1)
  ),
  100
);

We see again that the anonymous function receives itself as an argument and uses this argument to perform the recursive call. A combinator is used to pass this function to itself.

Of course, this isn’t really a thought experiment. Anonymous functions form the basis to lambda calculus, which forms the mathematical basic of computer science. By being able to perform complicated calculations (even recursion!) through simple, anonymous functions, lambda calculus provides a powerful system for analyzing computation in a mathematically convenient way.

None of this is new, by the way. Most of these ideas come from the work of Alonzo Church and Haskell Curry in the 1930s. In fact, the Y-combinator, namesake of the legendary startup accelerator Y Combinator, is an example of a combinator in lambda calculus, kind of like the one we derived above (though a little more complicated).

The Y-combinator is attributed to Haskell Curry and was instrumental in showing a mathematical inconsistency in untyped lambda calculus. Neat, eh?

For further reading, check out: https://en.wikipedia.org/wiki/Fixed-point_combinator

Specifically: https://en.wikipedia.org/wiki/Fixed-point_combinator#The_factorial_function

And: https://en.wikipedia.org/wiki/Lambda_calculus#Recursion_and_fixed_points