DIV CSS 佈局教程網

您现在的位置: DIV+CSS佈局教程網 >> 網頁腳本 >  >> JavaScript入門知識 >> AJAX入門 >> AJAX詳解
跟著 arden 一起學演算法——第五天:遞歸
編輯:AJAX詳解     

第五天 遞歸

今天我們一起來學一個常見又重要的主題——遞歸(recursion)。從這個主題出發,我們會認識一種特殊的資料結構:樹。數學裡早就引進過這個概念,它指的是一種能透過自己來表示的函式。通俗一點說,遞歸就是「呼叫自身的程式」。

最經典的例子莫過於階乘:

                      1         n=0;
    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 1;
     return N*fac(N-1);
}

我們從高中到大學的數學課上,做過不少需要找出 F(n)=Q(n)*F(n-1) 這類關係來求解的題目(其中 Q(n) 相對好算)。而在電腦裡使用遞歸,能用更簡潔的程式碼表達程式設計師的思路,而且良好的遞歸效率並不差——它的函式呼叫底層機制是透過堆疊來實現的。可以說,遞歸總能找到等價的非遞歸演算法,而且大部分的 for 迴圈都能轉化成一個遞歸式。

使用遞歸時要特別注意它的遞歸深度,深度過大可能導致遞歸無法完成。我們來看看遞歸的基本結構,它需要具備兩個要素:

  • 必須解決一個基本情況,例如階乘的 0! = 1;
  • 每次遞歸都要逼近這個基本情況,例如 n! = (n-1)! * n。

這樣一來,遞歸的正確性就能用歸納法來證明;至於階乘這種直接以定義式表達的,自然不必多贅一詞。

母牛問題

有一道經典的命題叫「母牛問題」:若一頭小母牛從出生第四年起,每年生一頭小母牛,按此規律,第 n 年時有多少頭母牛?

這個問題很適合用遞歸來表達人的思考方式。我們要找出一個描述母牛數量的數學等式。前三年裡還沒有新生小牛長成媽媽,三年之後才會不斷有小牛變成媽媽。於是式子可以這樣寫:N 年時牛的數量 = N-3 年時牛的數量 + N-1 年時牛的數量。其中 N-3 年前牛的數量,其實就是 N-1 年時牛媽媽的數量。再加上 N=1 時牛的數量為 1,如此分析,它就能套用上面的公式來求解了。

遞歸實現(C++):

//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 論壇上討論了很長一段時間,有興趣的朋友不妨去參與討論,網址為 https://www.chinaunix.net/jh/23/130156.html。

最後留給大家一個練習:Fibonacci 數列 1、1、2、3、5、8、13……請寫出求此數列第 N 項的遞歸演算法。答案就不寫了,上網搜尋一下,相關解說多得是。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved