Python中的遞迴｜學呀

Python中的遞迴

加至書籤

# Python中的遞迴

在上個章節中，我們學習了[遞迴的概念](/view/ad6c97ca9e?subj=python)，在這裡讓我們簡單地複習一下。程式中的遞迴，其實就是一個會不停呼叫自己的函數。這樣的函數，會不停地呼叫自己，直到達到想要的目標為止才結束運行。

讓我們用這個簡短的影片複習一下遞迴程式的概念。

::: youtube rf60MejMz3E
:::
 接著，讓我們來討論影片中出現，遞迴函數的經典例子—費氏數列：

## 費氏數列

在數學中，有一個經典的數列，叫做**費氏數列**（Fibonacci Sequence）。在這個數列中，第一項與第二項定義為 1，此後的每一項都等於前面兩項的合，將數列列出來，我們可以得到：

1、1、2、3、5、8、13、21……

如果我們製作一個函數 $f(x)$，並讓 $f(x)$ 等於費氏數列中第 x 項的值，那麼我們可以得到以下的數學定義：

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

## Python中的遞迴

接著，讓我們試著將上面對於費氏數列的定義變成 Python 的程式。我們的目標是建立一個函數，在輸入數字 x 時，輸出費氏數列的第 x 項。首先，讓我們從定義中簡單的部分開始：

$$f(1) = f(2) = 1$$

可以變成：

```
def f(x):  
    if x == 1 or x == 2:  
        return 1  
```
接著，我們加入遞迴的定義：

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

這個定義只有在 x 不等於 1 或 2 時才會成立，將其加入剛才的 if 判斷式，我們可以得到：

```
def f(x):  
    if x == 1 or x ==2:  
        return 1  
    else:  
        return f(x-1) + f(x-2)  
```
這麼一來，我們就可以試著使用這個函數。記得這個函數的定義嗎？在輸入 x 時，我們想要求得的是費氏數列中第 x 項的值。因此，我們可以試著列出費氏數列的前 10 項：

```
for i in range(1, 11):  
    print(f(i))  
```
因為 `range()` 回傳的是一個從** 0 開始的範圍**，而我們的數列是從第 1 項開始，而不是從第 0 項開始，因此我們使用的是 `range(1, 11)` 而不是 `range(10)`。執行這段程式後，我們將能得到這樣的輸出：

```
1  
1  
2  
3  
5  
8  
13  
21  
34  
55  
```
## 遞迴的效能問題

到目前為止，我們的費氏數列函數都運行的相當順暢，但是如果我們想要求得費氏數列中的第 150 項的值，會發生什麼事呢？我們用 `print()` 印出其值試試看：

```
print(f(150))  
```
你會發現，電腦遲遲都不給出一個結果，難道說程式的哪裡出了問題嗎？理論上，我們的程式並沒有問題，畢竟剛才在印出數列前 10 項時程式是運行順暢的。那為什麼數列第 150 項電腦跑不出來呢？讓我們再看一次程式：

```
def f(x):   
    if x == 1 or x ==2:   
        return 1   
    else:   
        return f(x-1) + f(x-2)    
```

其實原因很簡單，因為電腦算不出來—運算的次數太多，而且數字太大了！讓我們思考一下，假設現在要求得第 7 項，電腦在執行時，`f(x)` 函數會不停地呼叫自己，像這張圖所示：

![](https://d3i71xaburhd42.cloudfront.net/24720d0d6a8869a7674daf3860b2fd463f41a646/2-Figure3.1-1.png)

因此，在呼叫 `f(150)` 時，電腦因為運算的量太大，以致於遲遲沒有印出運算的結果。遞迴函數通常都會有類似的效能問題，因此在實際使用時，建議**盡量地少用具有遞迴結構的函數**。剛才我們所看到的費氏數列，是遞迴函數的一個經典題目，但其實有比遞迴更好的方法：

```
def f(x):   
    x -= 1   
    curr = [1, 1]   
    if x == 0 or x == 1:   
        return curr[x]   
    for i in range(2, x + 1):   
        curr.append(curr[i - 1] + curr[i - 2])   
    return curr[x]    
```
這樣的函數，雖然較剛才多了幾行，而且還多了列表的使用，但是在運算上卻能省下電腦極大的效能。

複製內容