斐波那契算法是最常见的递归算法，简单版本的代码如下：
long long fib(int n){
if(n <= 0) return 0;
if(n == 1) return 1;
return fib(n-1) + fib(n-2);
}
但显然这个算法的效率极低，因为在计算fib(n)和fib(n+1)的时候都会运算fib(n-2)，重复运算太多了。下面则是一个时间复杂度为o(n)的效率较高的算法：
long long fib(int n){
if(n <= 0) return 0;
if(n == 1) return 1;
long long fib1 = 0;
long long fib2 = 1;
long long fibN = 0;
for(int i = 2; i <= n; i++){
fibN = fib1 + fib2;
fib1 = fib2;
fib2 = fibN;
}
return fibN;
}
利用时间函数可以对比二者时间差距，前者完全没法看，第二种算法则是非常快速，下面是完整的代码：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
long long fib(int n){
if(n <= 0) return 0;
if(n == 1) return 1;
long long fib1 = 0;
long long fib2 = 1;
long long fibN = 0;
int i;
for(i = 2; i <= n; i++){
fibN = fib1 + fib2;
fib1 = fib2;
fib2 = fibN;
}
return fibN;
}
int main()
{
clock_t start,finish;
int i;
start = clock();
for(i = 0; i < 1000; i++){
printf("%lld ",fib(i));
}
finish = clock();
double runtime = (double)(finish-start);
printf("%runtime:%lf", runtime);
return 0;
}