斐波那契數(shù)列的實現(xiàn)
斐波那契問題介紹
如果一對兔子在出生兩個月后，就有繁殖能力，一對兔子每個月能生出一對小兔子來泉哈。假設(shè)所有兔子都不死，那么一年后可以繁殖多少對兔子破讨？
分析
| 所經(jīng)過的月數(shù) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 兔子對數(shù) | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | 144 |
表中的數(shù)字1丛晦，1，2提陶，3烫沙，5，8隙笆，13...構(gòu)成了一個序列斧吐，這個序列的特點是：前面兩個相鄰項之和 = 后一項.
用常規(guī)的迭代來實現(xiàn)
int main(int argc, const char * argv[]) {
int i;
int a[12];
a[0] = 0;
a[1] = 1;
printf("%d ",a[0]);
printf("%d ",a[1]);
for (i = 2; i<13; i++) {
a[i] = a[i-1]+a[i-2];
printf("%d ",a[i]);
}
printf("\n");
return 0;
}
輸出結(jié)果
用遞歸來實現(xiàn)
#include <stdio.h>
/**
* 斐波那契遞歸函數(shù)
*/
int Fib(int i){
if (i < 2)
return i == 0 ? 0 : 1;
return Fib(i - 1) + Fib(i - 2); // 這里Fib就是函數(shù)自己又固，它在自己調(diào)用自己
}
int main(int argc, const char * argv[]) {
for (int i = 0; i < 40; i++) {
printf("%d ", Fib(i));
}
printf("\n");
return 0;
}
同樣的問題用遞歸來實現(xiàn)，代碼很簡潔煤率。不過對于遞歸的理解有點費腦仰冠！
遞歸就是在函數(shù)中調(diào)用該函數(shù)本身的函數(shù)。
對于遞歸可以這樣理解：不用把一個遞歸函數(shù)中調(diào)用自己的函數(shù)看作是在調(diào)用自己蝶糯，而就當它是在調(diào)用另個一函數(shù)洋只，只不過這個函數(shù)和自己長的一樣。
遞歸
遞歸定義
一個直接調(diào)用自己或者通過一些列的語句間接調(diào)用自己的函數(shù)叫做遞歸函數(shù)昼捍。
遞歸注意點
- 每個遞歸定義必須至少有一個條件识虚，滿足時遞歸不再進行，即不再引用自身而是返回值退出妒茬。
- 遞歸使用的是選擇結(jié)構(gòu)担锤，迭代使用的是循環(huán)結(jié)構(gòu)。（這是迭代和遞歸的區(qū)別）
- 雖然遞歸是結(jié)構(gòu)更清晰簡潔乍钻，但是大量的遞歸調(diào)用會建立函數(shù)副本肛循，會消耗大量的時間和內(nèi)存。
遞歸的使用舉例
1.求n的階乘
int factorial(int n){
if (n == 0)
return 1;
else
return n * factorial(n - 1);
}
2.將輸入的任意長度的字符串反向輸出银择。以#作為輸入結(jié)束標志多糠。例如輸入字符串ABC，反向輸出字符串CBA浩考。
void printC(){
char a;
scanf("%c", &a);
if (a != '#') printC(); // 遞歸調(diào)用
if (a != '#') printf("%c", a); // 回退輸出
}
