递归Finbonacci优化

Question

编写下面的代码来计算前70个斐波纳契数.我有两个问题:

1)为什么程序对于每个连续的值变得越来越慢i？是因为调用具有高数字的函数会导致大量内存占用.

2)我可以使用什么技术或编码方案来加速运行时的程序计算？

#include <iostream>

int fib(int n) {
  if (n == 1 || n == 2) return 1;
  return fib(n - 1) + fib(n - 2);
}

void main() {
  for (int i = 1; i<70; i++)
    cout << " fib(" << i << ") = " << fib(i) << endl;
}

Answer 1

1)为什么程序对于每个连续的值变得越来越慢i？

简单地说,函数的更多递归调用会占用更多的时间来执行.

是因为调用具有高数字的函数会导致大量内存占用.

不,没有过多的内存占用(通过昂贵的动态内存分配操作).所需的所有内存都保留在堆栈中,该堆栈已经为进程预先分配.

尽管如此,您可能很容易耗尽可用的堆栈内存.

2)我可以使用什么技术或编码方案来加速运行时的程序计算？

递归可能不是解决该问题的最佳方法.这里有一个更详细的答案:

是否有比这更好的方法(性能)计算斐波那契？