【递归】实现斐波那契数列

斐波那契数列在递归中有一个很明显的缺点就是，在递归中，由于所有内存都是被提前占的，只有等到每项计算出来后才会释放该项所占的内存，所有对于斐波那契数列来说，光从数列看很适合递归，但是从计算机的运行速度上看，他的计算速度远远没有for循环时的运行速度快。 所以，“斐波那契数列是最像递归的不递归” 用FOR循环的算法 #include<stdio.h> int Fabio(int n) { int f1 = 1; int f2 = 1; int f3 = 1; for(int i=2;i<n;i++) { f3=f1+f2; f1=f2; f2=f3; } return f3; } int main() { printf("%d\n",Fabio(5)); printf("%d\n",Fabio(7)); printf("%d\n",Fabio(4)); return 0; }

用递归的算法 #include<stdio.h> int Fabio(int n) { if(n0||n1) { return 1; } int tmp=0; tmp=Fabio(n-1)+Fabio(n-2); return tmp; } int main() { printf("%d\n",Fabio(0)); printf("%d\n",Fabio(2)); printf("%d\n",Fabio(1)); printf("%d\n",Fabio(9)); return 0; }