Python中的遞迴

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

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

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

費氏數列

在數學中，有一個經典的數列，叫做費氏數列（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)。執行這段程式後，我們將能得到這樣的輸出：

遞迴的效能問題

到目前為止，我們的費氏數列函數都運行的相當順暢，但是如果我們想要求得費氏數列中的第 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) 函數會不停地呼叫自己，像這張圖所示：

因此，在呼叫 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]

這樣的函數，雖然較剛才多了幾行，而且還多了列表的使用，但是在運算上卻能省下電腦極大的效能。