跟踪递归函数被调用的次数 [英] Keep track of how many times a recursive function was called

问题描述

 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)

上面的代码采用一个整数，并通过乘以它自己的数字将其减少为一位数.

The code above takes an integer and reduces it to a single digit by multiplying it by its own digits.

示例为 39.

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

控制台会记录:

27 
14 
4

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

How do I keep track that the recursive function was called 3 times?

我已尝试添加计数器，但无法更新.将不胜感激任何帮助

I have tried adding a counter but it fails to update. Would appreciate any help

推荐答案

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

This is an almost purely academic variant, but you can use a modified fixed point combinator for this purpose.

让我们稍微缩短和改进您的原始函数:

Lets shorten and improve your original function a bit:

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

// singleDigit(123234234) == 0

从这个变体中，我们可以分解出递归调用并对其进行柯里化:

From this variant, we can factor out and curry the recursive call:

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

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

This function can now be used with a fixed point combinator; specifically I implemented a Y combinator adapted for (strict) JavaScript as follows:

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

我们有Ynormal(singleDigitF, 123234234) == 0.

现在诀窍来了.由于我们已经分解了对 Y 组合子的递归，我们可以计算其中的递归次数:

Now comes the trick. Since we have factored out the recursion to the Y combinator, we can count the number of recursions within it:

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

快速检查节点 REPL 给出:

A quick check in the Node REPL gives:

> 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风格编写的递归函数的调用次数.

This combinator will now work for counting the number of calls in any recursive function written in the style of singleDigitF.

(请注意，作为非常常见的答案有两个来源:数字溢出(123345456999999999 变成 123345457000000000 等)，以及您几乎肯定会当输入的大小增加时，在某处获取零作为中间值.)

(Note that there's two sources of getting zero as a very frequent answer: numeric overflow (123345456999999999 becoming 123345457000000000 etc.), and the fact that you will almost surely get zero as an intermediate value somewhere, when the size of the input is growing.)

这篇关于跟踪递归函数被调用的次数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！