究竟什麼是遞迴?



數學中的遞迴



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

    第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( x-1 ) + f( x-2)  $$
$$    f(1) = f(2) = 1  $$


程式中的遞迴


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


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

$$ f( x ) = f( x-1 ) + f( x-2) $$

會變成:

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

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

$$    f(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  複雜程度


遞迴的缺點


某些情況下,遞迴的確有它的用處,並且具有「簡單易讀懂」的特質。但是,很多的時候,遞迴會讓電腦的執行時間大幅延長,是一個效率極低的運算方法。例如上面例子中的費氏數列,是個遞迴的經典題目,但是倘若考慮運算的時間,一般人是不會使用遞迴的。
上一章節
下一章節
使用者分享的影片來自 YouTube。瞭解更多
+1 
感謝內容貢獻者 此篇文章由 1 位使用者共同編輯而成,並且由學呀的編輯團隊負責維護。點此查看編輯者名單。