下面的代码用于计算前 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;
}
最佳答案
1) Why does the program get increasingly slower for each successive value of
i
?
只是函数的递归调用越多,执行时间越长。
Is it because calling the function with high numbers causes heavy memory footprint.
不,没有过多的内存占用(通过昂贵的动态内存分配操作)。所有需要的内存都保存在堆栈中,堆栈已经为进程预先分配。
不过,对于稍大的数字,您可能很容易用完可用的堆栈内存。
2)What technique or coding scheme could I use to speed up the programs calculations at run time?
递归可能不是解决该问题的最佳方法。这里已经提供了更详细的答案:
Is there a better way (performance) calculate fibonacci than this one?
关于c++ - 递归 Finbonacci 优化,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36481190/