带有函数声明的递归JS

Question

关于函数表达式的递归有很多问题。有两种方法可以做到这一点：一是使用命名函数表达式，二是使用

arguments.callee

。但此时

arguments.callee

已被弃用。

问题是函数声明的递归怎么样。我们怎样才能从这个例子中删除

arguments.callee

并且不依赖于函数名称。

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

Answer 1

对于函数声明，没有内置机制来实现安全的自引用。如果函数被重命名，那么在函数体内使用该名称会导致错误

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

console.log(fib(8));

并且

arguments.callee

在严格模式下抛出错误：

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

console.log(fib(8));

但是，可以使用 Y 组合器（也称为 定点组合器）使任何递归函数与名称无关。简而言之，它允许函数调用自身而无需正式名称。在某些语言中，函数可能无法引用自身。在其他方面，比如 JavaScript，它可以。但是，您仍然可以利用 Y/定点组合器来避免 having 这样做。

该函数需要转换为采用一个参数，该参数将是其本身，然后返回一个使用该参数进行递归调用的函数。如果显示为箭头函数，那就更明显了：

//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        ^^^          ^^^

当使用函数声明时，它会是

//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);// |
  }//                  ^^^----------^^^-----<-----+
}

Y组合器本身的实现是

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

用法是

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

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(fib(8));
console.log(Y(updated)(8));
//          ^^^^^^^^^^

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