斐波那契数列可以采用递归和递推来计算,但递推的效率要远远高于递归的效率。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | #include <stdio.h> int c = 0; int f(int n) { c++; printf("%d\n", c); if (n==0 || n==1) return n; return f(n-1)+f(n-2); } int main(int argc, char *argv[]) { printf("%d\n", f(20)); return 0; } |
使用递推计算
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | #include <stdio.h> #define N 101 int main(int argc, char *argv[]) { int f[N]; int i, n; scanf("%d", &n); f[0] = 1; f[1] = 1; for (i=2; i<=n; i++) f[i] = f[i-1] + f[i-2]; printf("%d\n", f[n]); return 0; } |