# [資演] 2-遞迴
###### tags: `資演`


遞迴，指的是在一個函式中使用函式自己本身的方法。它的核心概念包含：
* 在不同大小的輸入上進行同樣的操作
* 每個步驟的輸入都更小，直到小到不能再小為止
* 當輸入小到不能再小的時候，就是遞迴的**終止條件**，此時這個問題的答案應該顯而易見，稱為base case

我們可以把遞迴反著看，則遞迴其實是一個從base case慢慢將整個問題建立起來的過程。

## 為什麼要用遞迴？
遞迴可以將一個大問題分成許多小問題，把問題變簡單。

特別地，在遇到樹或圖等資料結構時，你幾乎只能選擇使用遞迴的方式來解決問題。

## 遞迴 vs. 迴圈
我們現在來看一個最簡單的例子：寫一個函式來實作**階乘(factorial)**。

所謂的階乘，其定義如下：
\begin{equation}
n! = n\times(n-1)\times(n-2)\times \cdots\times1
\end{equation}

我們可以用一個迴圈來寫：

def factorial(n):
    if n == 0:
        return 1
    
    result = 1
    
    for i in range(1, n):
        result *= i
    return result

我們也可以使用遞迴來完成這個任務：

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1) 

在電腦裡面，遞迴是怎麼運作的呢？事實上，我們的電腦使用了一種叫做stack memory的機制。這個機制有點像我們在桌上疊上一張一張的便條紙，再由上而下解決每一張便條紙上的問題。假設我們現在呼叫了`factorial(5)`，則電腦進行的動作由下圖所示：

那麼，和迴圈相比，遞迴有什麼好處呢？我們可以從三個角度來比較遞迴和迴圈：
* 儲存空間
遞迴需要儲存stack memory的空間，而迴圈不用，所以在空間方面，迴圈勝！
* 時間效率
在跑遞迴程式碼時，遞迴需要額外的計算時間進行stack的pop操作，因此會比較慢，所以在時間方面，迴圈勝！
* 程式碼的簡潔程度
既然在時間空間上遞迴都輸了，遞迴總該有一個好處了吧，不然我們為什麼要用它？是的，從剛剛的例子看來，遞迴的程式碼簡單許多。在很多時候，從遞迴出發也比較容易構思，例如之後我們會學到的divide and conquer和dynamic programming等。
## 什麼時候該用遞迴？
當我們可以很簡單地把一個大問題分成許多小問題，並且我們不在乎需要多餘的計算時間與空間（也就是說，方便性是我們的主要考量）時。另外，在我們需要巡訪(traverse)整個樹或圖時，我們也會使用遞迴。

那麼，什麼時候我們**不該**用遞迴呢？首先，如果我們追求的是空間和時間的使用效率（例如你想在leetcode上贏過大家）時，那麼我們就不要選擇遞迴。特別是在嵌入式系統的場景下，空間的使用受到限制，因此必須盡量避免使用遞迴。

## 解決遞迴問題的三個步驟
在這裡我們同樣以階乘的例子來說明。
1. Recursive case
在這個步驟，我們先建立一個遞迴的流程。
`factorial(n) = n * factorial(n - 1)`
2. Base case
我們要知道遞迴什麼時候終止。
`factorial(0) = 1`
3. 例外與限制
`factorial(1.5)` --> ??
`factorial(-12)` --> ??
## 範例
我們可以再看一個例子：費波納契(Fibonacci)數列。

在數學上，費波那契數列是就是以遞迴的方法來定義的：


:::spoiler 程式碼

def fibonacci(n):
    assert n >=0 and int(n) == n , 'Fibonacci number cannot be negative number or non integer.'
    if n in [0,1]:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

:::