遞歸其實(shí)是?種解決問(wèn)題的方法，在C語(yǔ)言中，遞歸就是函數(shù)自己調(diào)用自己。

一、遞歸的介紹

1.1遞歸的思想

把?個(gè)大型復(fù)雜問(wèn)題層層轉(zhuǎn)化為?個(gè)與原問(wèn)題相似，但規(guī)模較小的子問(wèn)題來(lái)求解；直到子問(wèn)題不能再被拆分，遞歸就結(jié)束了。所以遞歸的思考方式就是把大事化小的過(guò)程。遞歸中的遞就是遞推的意思，歸就是回歸的意思。

1.2 遞歸的限制條件

遞歸在書(shū)寫(xiě)的時(shí)候，有2個(gè)必要條件：
? 遞歸存在限制條件，當(dāng)滿足這個(gè)限制條件的時(shí)候，遞歸便不再繼續(xù)。
? 每次遞歸調(diào)用之后越來(lái)越接近這個(gè)限制條件。

二、遞歸的例子

2.1求解n的階乘

?個(gè)正整數(shù)的階乘（factorial）是所有小于及等于該數(shù)的正整數(shù)的積，并且0的階乘為1。自然數(shù)n的階乘寫(xiě)作 n!。

通過(guò)分析可以發(fā)現(xiàn)n的階乘公式：n！ = n ? (n ? 1)!

實(shí)現(xiàn)如下：

int Fact(int n)
{if(n == 0)return 1;elsereturn n * Fact (n - 1);
}

這里的n不宜過(guò)大，否則會(huì)造成棧溢出。

2.2 順序打印數(shù)字的每一位

輸??個(gè)整數(shù)m，打印這個(gè)按照順序打印整數(shù)的每?位。
比如：
輸?：1234 輸出：1 2 3 4
輸?：520 輸出：5 2 0

如果n是?位數(shù)，n的每?位就是自己；n是超過(guò)1位數(shù)的話，就得拆分每?位。
實(shí)現(xiàn)如下：

void Print(int n)
{if(n>9){Print(n/10);}printf("%d ", n%10);
}

2.3斐波那契數(shù)列

代碼實(shí)現(xiàn)：

int Fib(int n)
{if(n<=2)return 1;elsereturn Fib(n-1)+Fib(n-2);
}

三、迭代與遞歸

在C語(yǔ)言中每?次函數(shù)調(diào)，都要需要為本次函數(shù)調(diào)用在棧區(qū)申請(qǐng)?塊內(nèi)存空間來(lái)保存函數(shù)調(diào)用期間的各種局部變量的值，這塊空間被稱為運(yùn)行時(shí)堆棧，或者函數(shù)棧幀。
函數(shù)不返回，函數(shù)對(duì)應(yīng)的棧幀空間就?直占用，所以如果函數(shù)調(diào)用中存在遞歸調(diào)用的話，每?次遞歸函數(shù)調(diào)用都會(huì)開(kāi)辟屬于自己的棧幀空間，直到函數(shù)遞歸不再繼續(xù)，開(kāi)始回歸，才逐層釋放棧幀空間。所以如果采用函數(shù)遞歸的方式完成代碼，遞歸層次太深，就會(huì)浪費(fèi)太多的棧幀空間，也可能引起棧溢出（stack overflow）的問(wèn)題。
這一部分的具體內(nèi)容會(huì)在下一篇博客中講述。

上述分析表明在一般情況下迭代效率遠(yuǎn)高于遞歸。

例如上面的2.3，輸入50這樣的數(shù)字時(shí)，需要很長(zhǎng)時(shí)間才能拿到我們想要的結(jié)果，因此優(yōu)化了該代碼：

int Fib(int n)
{int a = 1;int b = 1;int c = 1;while(n>2){c = a+b;a = b;b = c;n--;}return c;
}