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)。執行這段程式後,我們將能得到這樣的輸出:

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) 函數會不停地呼叫自己,像這張圖所示:

費氏數列運算效能 | 遞迴函數 | Python

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

這樣的函數,雖然較剛才多了幾行,而且還多了列表的使用,但是在運算上卻能省下電腦極大的效能。
上一章節
下一章節
使用者分享的影片來自 YouTube。瞭解更多
+1 
感謝內容貢獻者 此篇文章由 1 位使用者共同編輯而成,並且由學呀的編輯團隊負責維護。點此查看編輯者名單。