開啟「互動式 Python 執行列
程式中的遞迴
 課程目錄
 編輯章節
 EDU-MD
 Google 教室
 加至書籤

究竟什麼是遞迴?

數學中的遞迴


在我們用數學式子定義數列時,經常會使用到遞迴。例如當我們要定義費氏數列,每一項都等於前兩項的和,我們可以寫作:

第n項 = 第n-1項 + 第n-2項
    第1項 = 第2項 = 1

這麼一來,我們就可以定義出一個數列:1、1、2、3、5、8、13……
假設我們現在想要求得第1000項,依據定義第1000項 = 第999項 + 第998項,因此我們得求得第999項和第998項。但是問題又來了,我們若想知道第998項,又必須先知道997項和996項。如此一直循環下去,直到我們達到第2項和第1項。

這個不斷來回求值的過程,稱為遞迴。如果要把以上的數列寫作一個函數「f」,我們會得到:

f(x)=f(x1)+f(x2)f( x ) = f( x-1 ) + f( x-2)

f(1)=f(2)=1f( 1 ) = f( 2 ) = 1

程式中的遞迴

這個章節的重點,在於帶領讀者理解物件導向的概念,而非介紹單一個程式語法。此章節的程式語法和 JavaScript 等程式語言相近,但並非任何真實程式語言。請專注於章節中的概念部分,而非語法部分。


回想一下,程式中的函數,概念其實與數學的函數相同,也就是說,基本上只要數學定義得出來的函數,程式中也寫得出來。現在讓我們嘗試把上面的費氏數列寫作程式的函數。我們先寫簡單的部分:

f(x)=f(x1)+f(x2)f( x ) = f( x-1 ) + f( x-2)

會變成:

function f(x){
    return f(x - 1) + f(x - 2);
}

接著我們定義第1項以及第2項,也就是加入:

f(1)=f(2)=1f(1) = f(2) = 1

便得到:

function f(x){
    if(x == 1 || x == 2){
        return 1;
    }    return f(x - 1) + f(x - 2);
}

這麼一來,假設我們想要印出第15項,我們就可以說:

print(f(15));

接下來,用這個100秒的影片來確認自己對遞迴的了解吧。

recursive function  遞迴函數
infinite loop  無限迴圈
index  編號
complexity  複雜程度

遞迴的缺點

某些情況下,遞迴的確有它的用處,並且具有「簡單易讀懂」的特質。但是,很多的時候,遞迴會讓電腦的執行時間大幅延長,是一個效率極低的運算方法。例如上面例子中的費氏數列,是個遞迴的經典題目,但是倘若考慮運算的時間,一般人是不會使用遞迴的。

 均一平台
 台達磨課師
 酷課雲
 可汗學院
無相關資源
 收起側邊目錄
 
前往目錄頁面