Python中的遞迴
 課程目錄
 編輯章節
 EDU-MD
 Google 教室
 加至書籤

Python中的遞迴

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

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

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

費氏數列

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

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

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

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

f(x)=f(x1)+f(x2)f(x) = f(x - 1) + f(x - 2)

Python中的遞迴

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

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

可以變成:

def f(x):  
    if x == 1 or x == 2:  
        return 1  

接著,我們加入遞迴的定義:

f(x)=f(x1)+f(x2)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) 函數會不停地呼叫自己,像這張圖所示:

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

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

 均一平台
 台達磨課師
 酷課雲
 可汗學院
無相關資源
 收起側邊目錄
 
前往目錄頁面