跟踪递归函数被调用的次数

Question

 function singleDigit(num) {
      let counter = 0
      let number = [...num + ''].map(Number).reduce((x, y) => {return x * y})

      if(number <= 9){
          console.log(number)
      }else{
          console.log(number)
          return singleDigit(number), counter += 1
      }
   }
singleDigit(39)

上面的代码接受一个整数，并通过将其乘以自己的数字将其减少为一个数字。

例如39。

3 x 9 = 27.
2 x 7 = 14.
1 x 4 = 4.

控制台将记录：

27 
14 
4

如何跟踪递归函数被调用了3次？

我尝试添加计数器，但无法更新。非常感谢您的帮助

Answer 1

这几乎是一个纯粹的学术变体，但您可以为此使用修改后的定点组合器。

让我们稍微缩短和改进您的原始功能：

function singleDigit(n) {
    let digitProduct = [...(n + '')].reduce((x, y) => x * y, 1);
    return digitProduct <= 9 ? digitProduct : singleDigit(digitProduct);
}

// singleDigit(123234234) == 0

从这个变量中，我们可以计算出递归调用并进行curry：

function singleDigitF(recur) {
    return function (n) {
        let digitProduct = [...(n + '')].reduce((x, y) => x * y, 1);
        return digitProduct <= 9 ? digitProduct : recur()(digitProduct);
    };
}

此函数现在可以与定点组合器一起使用；具体来说，我实现了一个适用于（严格）JavaScript的Y组合器，如下所示：

function Ynormal(f, ...args) {
    let Y = (g) => g(() => Y(g));
    return Y(f)(...args);
}

其中，我们有Ynormal（singleDigitF，123234234）==0。

现在是诀窍。由于我们已经将递归分解为Y组合符，因此我们可以计算其中的递归数：

function Ycount(f, ...args) {
    let count = 1;
    let Y = (g) => g(() => {count += 1; return Y(g);});
    return [Y(f)(...args), count];
}

节点REPL中的快速检查提供：

> Ycount(singleDigitF, 123234234)
[ 0, 3 ]
> let digitProduct = (n) => [...(n + '')].reduce((x, y) => x * y, 1)
undefined
> digitProduct(123234234)
3456
> digitProduct(3456)
360
> digitProduct(360)
0
> Ycount(singleDigitF, 39)
[ 4, 3 ]

这个组合器现在可以计算以singleDigitF风格编写的任何递归函数中的调用数。

（请注意，零作为一个非常常见的答案有两个来源：数字溢出（123345456999999999变成123345457000000000等），以及当输入的大小正在增长时，您几乎肯定会在某个地方获得零作为中间值。）

Answer 2

传统的解决方案是将计数作为参数传递给另一个答案所建议的函数。

然而，js中还有另一个解决方案。其他一些答案建议只在递归函数之外声明count：

let counter = 0
function singleDigit(num) {
  counter++;
  // ..
}

这当然有效。但是这使得函数不可重入（不能正确调用两次）。在某些情况下，您可以忽略这个问题，只需确保您不会调用singleDigit两次（javascript是单线程的，所以并不难做到），但如果您稍后更新singleDigit以异步，这是一个等待发生的错误，而且感觉也很难看。

解决方案是在外部而不是全局声明计数器变量。这是可能的，因为javascript具有闭包：

function singleDigit(num) {
  let counter = 0; // outside but in a closure

  // use an inner function as the real recursive function:
  function recursion (num) {
    counter ++
    let number = [...num + ''].map(Number).reduce((x, y) => {return x * y})

    if(number <= 9){
      return counter            // return final count (terminate)
    }else{
      return recursion(number)  // recurse!
    }
  }

  return recursion(num); // start recursion
}

这与全局解决方案类似，但每次调用单位数（现在不是递归函数）时，都会创建计数器变量的新实例。

Answer 3

您应该在函数定义中添加一个反参数：

function singleDigit(num, counter = 0) {
    console.log(`called ${counter} times`)
    //...
    return singleDigit(number, counter+1)
}
singleDigit(39)