#include<stdio.h>

long long int Fibonacci(int n)
{
    long long int y;
    if(n<=2)
        y=1;
    else
        y=Fibonacci(n-1)+Fibonacci(n-2);
    return(y);
}

int main()
{
    long long int n,F;
    scanf("%d",&n);
    F=Fibonacci(n);
    printf("%d",F);
    return 0;
}
这段代码输入时结果没错，但输出太慢，输入40时得等5秒钟，输入60等了一分钟都没出结果

求斐波那契数列第n项用递归函数写除了可读性更好点，与for循环相比一点优势都没有。
时间上， 执行调用与返回的额外工作要占用CPU时间。空间上，随着每递归一次，栈内存就多占用一截。
你可以统计下输入40时递归函数的调用次数，与时间的关系，然后逐渐增加n的数值，看看统计的次数变化有多大。

要求必须用递归

一个递归函数里面包含了两个子递归点,正常情况下总递归次数以指数的的形式增长，指数幂为该数的增长率，斐波那契数列的和以每一项无穷接近根号2的倍率增长，递归次数同样也以无限接近根号2的倍率增长，输入40要等待5秒，输入60要等待5^10秒，就是9765625秒，折合起来约为113天时间~笑了~
你有时间可以去比划一下斐波那契数列的递归过程~

[此贴子已经被作者于2016-11-25 03:29编辑过]

怎么这么多人刷屏啊~上贴分明就是说错了，输入60明明是5*2^10秒，5120秒，一个多小时就可以了~纯属口误~

long long int n,F;
scanf("%d",&n);
这个起先就错了吧

要求必须用递归 ------ 那就别抱怨速度慢呀

给个我以前写的（顺便说一下，如果最大40项的话，根本用不到long long）

#include <stdio.h>

unsigned long long fibonacci( unsigned first, unsigned second, size_t n )
{
    // a *= b
    #define MUL(a,b) do {\
        unsigned long long t00 = a##00*b##00+a##01*b##10;\
        unsigned long long t01 = a##00*b##01+a##01*b##11;\
        unsigned long long t10 = a##10*b##00+a##11*b##10;\
        unsigned long long t11 = a##10*b##01+a##11*b##11;\
        a##00=t00, a##01=t01, a##10=t10, a##11=t11;\
    } while(0)

    unsigned long long r00=1,r01=0,r10=0,r11=1;
    for( unsigned long long v00=0,v01=1,v10=1,v11=1; n!=0; n/=2 )
    {
        if( n%2 == 1 )
            MUL(r,v); // r*=v
        MUL(v,v); // v*=v;
    }
    return r00*first + r01*second;

    #undef MUL
}

int main( void )
{
    printf( "%llu\n", fibonacci(1,1,39) ); // fibonacci数列第40项的值是 102334155

    return 0;
}