Recursion with function declaration JS

Question

There are many questions about recursion with function expressions. And there are two ways to do it: One is using named function expression and second is using arguments.callee. But at this time arguments.callee is deprecated.

The question is what about recursion with function declaration. How can we remove arguments.callee from this example and not be depended on the function name.

function fib(n){
   return n < 3 ? 1 : arguments.callee(n - 1) + arguments.callee(n - 2);
}

Answer 1

For function declarations there is no built-in mechanism to have safe self-reference. If the function is renamed, then using the name inside the body would be lead to an error

function fib_renamed(n){
   return n < 3 ? 1 : fib(n - 1) + fib(n - 2);
// used to be correct ^^^          ^^^
}

console.log(fib(8));

And arguments.callee throws an error in strict mode:

function fib(n){
  "use strict";
   return n < 3 ? 1 : arguments.callee(n - 1) + arguments.callee(n - 2);
}

console.log(fib(8));

However, any recursive function can be made name-agnostic with the Y combinator (also called fixed-point combinator). Put simply it allows for a function to call itself without needing to have a formal name. In some languages it might not be possible for a function to refer to itself. In others, like JavaScript, it can. However, you can still leverage the Y/fixed-point combinator to avoid having to do that.

The function would need to be transformed to take one parameter which will be itself and then returns a function that uses said parameter for recursive calls. It is a bit more obvious if shown as an arrow function:

//original
const fib = n => n < 3 ? 1 : fib(n - 1) + fib(n - 2);
// calls itself              ^^^          ^^^

//updated
const updated = fib => 
//              ^^^ takes a function to call as parameter
             n => n < 3 ? 1 : fib(n - 1) + fib(n - 2);
// calls the parameter        ^^^          ^^^

While using function declarations it will be

//original
function fib(n){
   return n < 3 ? 1 : fib(n - 1) + fib(n - 2);
}

//updated
function updated(fib) {
//               ^^^---->---->---->----->----->---+
  return function (n){//                          |
  //             ^ no name needed                 v
    return n < 3 ? 1 : fib(n - 1) + fib(n - 2);// |
  }//                  ^^^----------^^^-----<-----+
}

The implementation of the Y combinator itself is

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

(from "Common combinators in JavaScript" by Avaq on GitHub)

And the usage is:

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

function updated(fib) {
  return function (n){
    return n < 3 ? 1 : fib(n - 1) + fib(n - 2);
  }
}

console.log(Y(updated)(8));
//          ^^^^^^^^^^

//also possible:
const fib_new = Y(updated);
console.log(fib_new(8));

Answer 2

U combinator

By passing a function to itself as an argument, a function can recur using its parameter instead of its name! So the function given to U should have at least one parameter that will bind to the function (itself).

const U = f => f(f)
  
U(a => console.log(a))

// output:
// a => console.log(a)

1. f is assigned to a => console.log(a) and U calls f(f)
2. when f runs, it logs its only parameter a to the console
3. as we know, a is f
4. ie, f knows itself by means of a, without arguments.callee or name

Here's a minimal, terminating program -

const U = f => f(f)

const countDown = recur => x =>
  x == 0
    ? "blast off!"
    : x + ", " + U(recur)(x - 1)
    
const ans =
  U(countDown)(10)
  
console.log(ans)
// 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, blast off!

Of course it works in the case where arguments.callee or the function's name would be referenced more than once. Take the classic fib example -

const U = f => f(f)

const fib = recur => x =>
  x < 2
    ? x
    : U(recur)(x - 1) + U(recur)(x - 2)

const ans =
  U(fib)(10)
  
console.log(ans) // 55

By use of currying, you can easily construct functions with more parameters -

const U = f => f(f)

const range = recur => min => max =>
  min == max
    ? []
    : [min, ...U(recur)(min + 1)(max)]
    
const fold = recur => init => f => xs =>
  xs.length == 0
    ? init
    : U(recur)(f(init,xs[0]))(f)(xs.slice(1))

const add = (x, y) =>
  x + y

const numbers =
  U(range)(7)(14)
  
const sum =
  U(fold)(0)(add)(numbers)
  
console.log(numbers, sum)
// [7, 8, 9, 10, 11, 12, 13]
// 70

U is the primordial essence from which the more sophisticated Y combinator is derived. See this related Q&A for more.