意大利的數學家列昂那多·斐波那契在1202年研究兔子產崽問題時發現了此數列．設一對大兔子每月生一對小兔子，每對新生兔在出生一個月后又下崽，假若兔子都不死亡．問：一對兔子，一年能繁殖成多少對兔子？題中本質上有兩類兔子：一類是能生殖的兔子，簡稱為大兔子；新生的兔子不能生殖，簡稱為小兔子；小兔子一個月就長成大兔子．求的是大兔子與小兔子的總和。

月份ⅠⅡⅢⅣⅤⅥⅦⅧⅨⅩⅪⅫ

大兔對數1123581321345589144

小兔對數01123581321345589到十二月時有大兔子144對，小兔子89對，共有兔子 144+89=233對從上表看出：

① 每月小兔對數=上月大兔對數。②每月大兔對數等于上個月大兔對數與小兔對數之和．綜合①②兩點，我們就有：每月大兔對數等于前兩個月大兔對數之和．

如果用 un 表示第 n 月的大兔對數，則有

un = un-1 +un-2,n >2每月大兔對數un 排成數列為：1，1，2，3，5，8，13，21，34，55，89，144，此數列稱為斐波那契數列．

遞歸法：

使用公式f[n]=f[n-1]+f[n-2]，依次遞歸計算，遞歸結束條件是f[1]=1，f[2]=1。

代碼示例：#include

using?namespace?std;

long?long?Fib(int?n)

{

if?(n?==?0)

{

return?0;

}

else?if?(n?==?1)

{

return?1;

}

else?if(n?>?1)

{

return?Fib(n?-?1)?+?Fib(n?-?2);

}

//return?n?>?1???Fib(n?-?1)?+?Fib(n?-?2)?:?n;?//條件運算符簡單，一行代碼即可

}

void?Test()

{

int?N?=?0;

scanf("%d",?&N);

int?ret?=?Fib(N);

printf("%d\n",?ret);

}

int?main()

{

Test();

system("pause");

return?0;

}

但是，遞歸法解決此問題并非高效，下面我們看看非遞歸法。

非遞歸法：

迭代實現是最高效的，時間復雜度是n*1 = 0(n)，空間復雜度是0(1)。#include

using?namespace?std;

long?long?Fib(int?n)

{

if?(n?==?0)

{

return?0;

}

else?if?(n?==?1)

{

return?1;

}

else?if?(n?>?1)

{

int?a?=?1;

int?b?=?1;

int?c?=?1;

for?(int?i?=?2;?i?

{

c?=?a?+?b;

a?=?b;

b?=?c;

}

return?c;

}

}

void?Test()

{

int?N?=?0;

scanf("%d",?&N);

int?ret?=?Fib(N);

printf("%d\n",?ret);

}

int?main()

{

Test();

system("pause");

return?0;

}

總結

以上是生活随笔為你收集整理的递归函数就兔子数C语言,【C语言】求斐波那契(Fibonacci)数列通项（递归法、非递归法）...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。