javascript - 如何向我的斐波那契数列添加停止指令？

Question

我正在尝试使用递归来制作斐波那契算法。我想将所有斐波那契数列打印到此 res 变量，并在超过此 num 参数时停止。我想知道我该如何做到这一点？这段代码:

function fibs(num) {
    let i = 2;
    let res = 0;
    while (res < num) {
        res = fibs(i - 1) + fibs(i - 2);
        i++;
    }
    return res;
}
console.log(fibs(10));

我收到超出最大调用堆栈大小的错误。

Answer 1

注释:

⚠️ 通过使用第一个解决方案，虽然有一些小错误，例如添加一个大数字，但您仍然可以超过最大调用堆栈大小。如果你想想递归函数的意义，它一次又一次地调用自身，而且它的计算时间很长。

👌 使用第二种解决方案，从技术上讲，您仅使用当前堆栈来计算结果。功能看起来更大但并不昂贵。

解决方案:

第一个解决方案 - 递归:

如果您仍然想使用递归解决方案，则此解决方案比原始解决方案简单得多:

const fibs = (num) => {
  if (num === 1 || num === 2) {
     return 1;
  }
     
  return fibs(num - 1) + fibs(num - 2);
};

// 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
for (let i = 1; i <= 10; i++) {
 console.log(`fibs(${i}):`, fibs(i)); 
}

第二种解决方案 - 非递归:

总有更好的解决方案，如果我打赌我宁愿选择非递归解决方案，请在下面找到一个示例:

const fibs = (num) => {
  if (num === 1 || num === 2) {
     return 1;
  }

  let result = 1;
  let resultPrevious = 1;
  
  for(let i = 2; i < num; i++) {
    const temp = result;
    result += resultPrevious;
    resultPrevious = temp;
  }
  
  return result;
};

// 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
for (let i = 1; i <= 10; i++) {
 console.log(`fibs(${i}):`, fibs(i)); 
}

我感兴趣的是，在运行 fibs(30) 的情况下，非递归解决方案如何更快，请查看下面的结果:

从结果来看，在测试值 30 时，递归解决方案似乎慢了 98.86%。

希望这会有所帮助!