問
機
器
人
機
器
人
開啟「互動式 Python 執行列」
究竟什麼是遞迴?
數學中的遞迴
在我們用數學式子定義數列時,經常會使用到遞迴。例如當我們要定義費氏數列,每一項都等於前兩項的和,我們可以寫作:
第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」,我們會得到:
程式中的遞迴
這個章節的重點,在於帶領讀者理解物件導向的概念,而非介紹單一個程式語法。此章節的程式語法和 JavaScript 等程式語言相近,但並非任何真實程式語言。請專注於章節中的概念部分,而非語法部分。
回想一下,程式中的函數,概念其實與數學的函數相同,也就是說,基本上只要數學定義得出來的函數,程式中也寫得出來。現在讓我們嘗試把上面的費氏數列寫作程式的函數。我們先寫簡單的部分:
會變成:
function f(x){
return f(x - 1) + f(x - 2);
}
接著我們定義第1項以及第2項,也就是加入:
便得到:
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 複雜程度
遞迴的缺點
某些情況下,遞迴的確有它的用處,並且具有「簡單易讀懂」的特質。但是,很多的時候,遞迴會讓電腦的執行時間大幅延長,是一個效率極低的運算方法。例如上面例子中的費氏數列,是個遞迴的經典題目,但是倘若考慮運算的時間,一般人是不會使用遞迴的。
無相關資源
收起側邊目錄
前往目錄頁面