第五天 遞歸
今天我們一起學習遞歸這個常見的命題。從這個命題中我們學習這樣一種特殊的數據結構：樹。在學習數學的時候引來了這個概念，它表示一個可以通過自己來表示的函數。比較通俗的定義是：調用自身的程序。
最常見的一個例子是階乘：
F(n)=
F(n-1) n>=1;
如果直接計算，可以使用一個循環：for(n=1,s=1; n<=N; n++) s*=n; 這也是按照數學定義式來計算的，但是將這兩個表達放在一起也需要人的思維整合過程。下面使用遞歸的方法可以更加直觀的表示其定義：Int fac(int N)
{
If (N==0) return 0;
return N*fac(N-1);
}
我們在高中、大學的數學課上都做過很多，需要找到F(n)=Q(n)*F(n-1)這樣關系來解決的問題(Q(n)相對比較好計算)。而在計算機中使用遞歸可以使用更簡潔的代碼表達程序員的思想，並且良好的遞歸效率並不差（其函數調用底層機制是使用下堆棧來實現的）。可以看到，遞歸總是可以找到等同的非遞歸算法。而且大部分的for循環都可以轉化成一個遞歸式。
使用遞歸需要注意的是它的遞歸深度。這可能導致我們的遞歸無法完成。
我們來看看遞歸的基本結構：它需要解決一個基本的情況：如階乘的0！=1
2、 每次遞歸都需要逼近基本的情況： n！=(n-1)!*n；
這樣遞歸的正確性我們可以使用歸納法來證明，階乘這樣的直接用定義式來表達的就不需要證明了吧。
有一個命題叫母牛問題：
若一頭小母牛, 從出生第四年開始每年生一頭小母牛,按此規律,第n年時有多少頭母牛
這個問題可以很好的使用遞歸方法表達人的思考方式。我們在解決此問題時需要找到一個表示母牛數量的數學等式。前面3年中，沒有新的小牛成為媽媽。那麼3年後，不斷有小牛變成媽媽。我們來這樣寫此表達式：N年時牛的數量=N-3年時牛的數量+N-1年時牛的數量。 N-3年前牛的數量其實就是N-1年時牛媽媽的數量。並且有N=1時，牛的數量為count。如此分析，它可以套用上面的公式來解決問題了。 cpp遞歸實現：
//this function is write by zhouhuahai(大草原) in CSDN
int getNumber(int years)
{
if(years<4 && years>=0)
return 1;
else
return getNumber(years-1)+getNumber(years-3);
}
這裡還有一個非遞歸的算法，大家可以比較參考下。
// this function write by pomelowu(羽戰士) in CSDN
int GetBaby (int n)
{
int sum = 0;
if (n >= 4)
{
for(int i = 1; i <= n - 4 + 1; i ++)
{
sum ++;
sum += GetBaby(i); //雖然不是遞歸這裡卻也調用了自己仍然有遞歸的成分在裡面
}
}
return sum;
}
上面的兩個程序來自CSDN的兩位朋友。這個問題在chinaunix板塊上討論了很長時間。有興趣的朋友可以去參加一下。地址： http://www.chinaunix.Net/jh/23/130156.Html
給大家留個練習：fibonacci數列：1，1，2，3，5，8，13 … 請給出來此數列的第N項遞歸算法。不寫答案了，去google上自己search下，太多了。