程式中的遞迴｜學呀

程式中的遞迴

加至書籤

# 究竟什麼是遞迴？
## 數學中的遞迴
![](https://miro.medium.com/max/664/1*xd2O7AZm_ZVJrS3-0JyDDg.png)
在我們用數學式子定義數列時，經常會使用到遞迴。例如當我們要定義**費氏數列**，每一項都等於前兩項的和，我們可以寫作：

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

## 程式中的遞迴
::: suggestion
這個章節的重點，在於帶領讀者理解物件導向的概念，而非介紹單一個程式語法。此章節的程式語法和 JavaScript 等程式語言相近，但並非任何真實程式語言。請專注於章節中的概念部分，而非語法部分。
:::
![](https://www.bennadel.com/resources/uploads/cfdump/cfdump_recursion_problem_9_levels_deep.gif)
回想一下，程式中的函數，概念其實與數學的函數相同，也就是說，基本上只要數學定義得出來的函數，程式中也寫得出來。現在讓我們嘗試把上面的費氏數列寫作程式的函數。我們先寫簡單的部分：
$$ 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秒的影片來確認自己對遞迴的了解吧。
::: youtube rf60MejMz3E
:::
::: translation

recursive function  遞迴函數
infinite loop  無限迴圈
index  編號
complexity  複雜程度
:::
## 遞迴的缺點
某些情況下，遞迴的確有它的用處，並且具有「簡單易讀懂」的特質。但是，很多的時候，遞迴會讓電腦的執行時間大幅延長，**是一個效率極低的運算方法**。例如上面例子中的費氏數列，是個遞迴的經典題目，但是倘若考慮運算的時間，一般人是不會使用遞迴的。

複製內容