菲波拉契数列是典型的问题，几乎出现于所有有关程序设计和算法等的书籍中。

菲波拉契数列与杨辉三角也是有关系的，看以下这张图就知道了。

菲波拉契数列的递归定义如下：

f(0)=0 n=0

f(1)=1 n=1

f(n)=f(n-2)+f(n-1) n>=2

当n比较大之后，菲波拉契数列的f(n-1)/f(n)则接近于黄金分割数0.618。

菲波拉契数列不仅仅有这两种计算法，其他的计算方法相对比较复杂。

程序中使用条件编译，可以计数递归调用的次数和递推循环的次数，可以比较算法复杂度。

相关文章链接：

/* * * 计算斐波拉契数列第n项的两种（递归和递推）算法程序 * */#include 
    
     #define DEBUG#ifdef DEBUGint c1=0, c2=0;#endiflong fib1(int);long fib2(int);int main(void){    int n = 10;    printf("fib1(%d)=%ld\n", n, fib1(n));    printf("fib2(%d)=%ld\n", n, fib2(n));#ifdef DEBUG    printf("c1=%d  c2=%d\n", c1, c2);#endif    return 0;}/* 递归法：计算斐波拉契数列的第n项 */long fib1(int n){#ifdef DEBUG    c1++;#endif    return (n==0 || n == 1)?n:fib1(n-2) + fib1(n-1);}/* 递推法：计算斐波拉契数列的第n项 */long fib2(int n){    if(n==0 || n == 1)        return n;    long f0 = 0, f1 = 1, temp;    int i;    for(i=2; i<=n; i++) {#ifdef DEBUG        c2++;#endif        temp = f0 + f1;        f0 = f1;        f1 = temp;    }    return temp;}