为什么这个递归函数超过调用堆栈大小？

Question

我正在尝试编写一个函数来查找 1 到 20 之间的所有整数相除的最小数。（我们称此条件为 D）

这是我的解决方案，它以某种方式超出了调用堆栈大小限制。

function findSmallest(num){
    var count = 2
    while (count<21){
        count++
        if (num % count !== 0){
            // exit the loop
            return findSmallest(num++)
        }

    }
    return num
}

console.log(findSmallest(20))

我的推理在某些地方是错误的，但这是我的看法（请纠正我错误的地方）：

使用不满足条件 D 的数字 N 调用此函数将导致使用 N + 1 再次调用该函数。最终，当它达到应满足条件 D 的数字 M 时，while 循环运行一直到函数返回数字 M 并且没有更多的递归调用。

但我在运行上收到此错误：

function findSmallest(num){ ^

RangeError: Maximum call stack size exceeded

我知道像这样的错误几乎总是由于递归函数没有达到基本情况。这是这里的问题，如果是，问题出在哪里？

Answer 1

我发现了两个错误。

在你的 while 循环中，count 的值是 3 到 21。
num的值在循环中改变。 num++ 应该是 num + 1

但是，即使修复了这些错误，也无法解决错误。答案是232792560。本次递归深度过大，栈内存耗尽

例如，此代码会导致相同的错误。

function foo (num) {
    if (num === 0) return
    else foo(num - 1)
}

foo(232792560)

不用递归编码可以避免错误。

Answer 2

您的问题是您输入递归超过 2 亿次（加上之前答案中发现的错误）。您要查找的数字是所有素数乘以它们在定义范围内的每个数字中出现次数最多的倍数。所以这是您的解决方案：

function findSmallestDivisible(n) {
    if(n < 2 || n > 100) {
    throw "Numbers between 2 and 100 please";
  }
    var arr = new Array(n), res = 2;
  arr[0] = 1;
  arr[1] = 2;
  for(var i = 2; i < arr.length; i++) {
    arr[i] = fix(i, arr);
    res *= arr[i];
  }
  return res;
}

function fix(idx, arr) {
    var res = idx + 1;
  for(var i = 1; i < idx; i++) {
    if((res % arr[i]) == 0) {
        res /= arr[i];
    }
  }
  return res;
}

https://jsfiddle.net/7ewkeamL/

为什么这个递归函数超过调用堆栈大小？

Why is this recursive function exceeding call stack size?

recursion

runtime-error

division

stack-size