究竟什麼是遞迴？

數學中的遞迴

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

第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$

程式中的遞迴

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

$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秒的影片來確認自己對遞迴的了解吧。

遞迴的缺點

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