结束递归的有效方法

Question

我试图定义一个递归函数，如果给定输入的平方和为1，则返回X，这很好。然而，如果输入没有导致1，那么它会一直循环，我找不到退出它的方法

例如，整数7、10、13的输入导致1，但2、3、4、5、6、11的输入不导致1。如果我尝试x === 4 || x === 0，它结束了不导致1的输入的递归，但对于某些输入，需要多次递归调用才能达到4，这并不有效。稍后，我想将返回值用于其他计算。

function recursion(x) {
if (x === 0) {
return;
}
if (x === 1) {
return x;
}
x = squareSum(x);
return recursion(x);
}

这是squareSum函数。

function sqaureSum(n){
let sumTotal;
if (n < 10){
sumTotal = Math.pow(n, 2);
return sumTotal;
}
sumTotal = Math.pow(n % 10, 2) + squareSum(Math.floor(n / 10));
return sumTotal;
}

Answer 1

您需要跟踪您已经看到的数字，当您到达1或到达您已经看到过的数字时停止。

我们可以添加一个默认参数和一个已经看到的数字列表，然后在递归调用中，将当前数字添加到该列表中。这个版本只返回一个布尔值，如果数字最终达到1，则返回true，如果我们达到其他循环，则返回false。我们找到了前一百个正整数中的数字，这些数字确实减少到1:

const squareSum = (n) => 
(n) < 10 ? n * n : (n % 10) ** 2 + squareSum (Math .floor ( n / 10))
const repeatedSquareSum = (n, seen = []) => 
n <= 1 
? true
: seen .includes (n) 
? false
: repeatedSquareSum (squareSum (n), [...seen, n])
console .log (Array .from ({length: 100}, (n, i) => i + 1) .filter (n => repeatedSquareSum(n)))

您希望在正数的情况下返回原始数字。这很奇怪，但并不难：

const repeatedSquareSum = (n, seen = []) => 
n <= 1 
? seen [0] || n
: seen .includes (n) 
? false
: repeatedSquareSum (squareSum (n), [...seen, n])

(|| n位只是因为在0和1的情况下，我们还没有向seen添加任何内容。)

您还可以返回在false情况下访问的数字数组，在这种情况下返回seen而不是false，或者如果您只想看到数字的重复循环，您可以返回[...seen .slice (seen.indexOf (n)), n]。

其他注释指出，在0 -> 0和1 -> 1之外，只有一个重复值循环。这就是4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4。这个有点令人惊讶的结果在一篇可读性很强的正式数学论文中得到了证明。利用这些信息，我们可以选择编写一个更简单的版本：

const repeatedSquareSum = (n) =>
n <= 1 
? true 
: n == 4 
? false 
: repeatedSquareSum (squareSum (n))

更新

评论中的一个后续问题(下次，请开始一个新问题)询问如何计算步骤数，直到我们达到20这样的目标数字。我们可以使用count添加一个默认参数，并跟踪直到达到该数字或进入循环。唯一的复杂性是，如果目标在无休止循环的数字列表中，我们不需要在进入循环时停止，而只需要在达到目标数字时停止。

为了简单起见，我们在上面的最后一个版本上构建了这个，但我们也可以在更早、更复杂的版本上这样做：

const squareSum = (n) => 
(n) < 10 ? n * n : (n % 10) ** 2 + squareSum (Math .floor ( n / 10))
const squareSumToTarget = (target) => (n, count = 0) =>
n <= 1 || (![4, 16, 37, 58, 89, 145, 42, 20] .includes (target) && n == 4)
? Infinity
: n == target 
? count 
: squareSumToTarget (target) (squareSum (n), count + 1)
const squareSumTo20 = squareSumToTarget (20)
console .log (squareSumTo20 (445566)) //=> 3 (445566 -> 154 -> 42 -> 20)
console .log (squareSumTo20 (44)) //=> Infinity (44 -> 32 -> 13 -> 10 -> 1 -> 1 -> 1 -> ...)
console .log (squareSumTo20 (4)) //=> 7 (4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20)
console .log (squareSumToTarget (17) (79)) //=> Infinity (79 -> 130 -> 10 -> 1 -> 1 -> 1 -> ...) 
console .log (squareSumToTarget (36) (5) )
//=> Infinity (36 -> 45 -> 41 -> 17 -> 50 -> 25 -> 29 -> 85 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16 -> 37 -> 58 -> 89 ...)
//                                                              ^----------------------------------------------'

Answer 2

因为sumTotal = Math.pow(n % 10, 2) + squareSum(n / 10);当你计算n / 10时，它可以是一个浮点值，你应该将你的数字转换为int

用于检查recursion内的float数字log x

function recursion(x) {
console.log(x) // <-- HERE
...
}

Math.floor、Math.ceil、Math.round可以帮助您

和

if (x === 0) {
return;
}

在CCD_ 27内部加一个值(0或1)。返回undefiend并转换为NaN

Answer 3

搜索几分钟，我发现了这个util信息。总之，你可以检查你得到的数字在某个点上是否等于这些数字中的任何一个：4、16、37、58、89、145、42、20：

const loopNumbers = new Set([4, 16, 37, 58, 89, 145, 42, 20]);
...
if(loopNumbers.has(x)) {
// It does not lead to 1
}