慶祝學呀
百萬
造訪!
尚未建立名稱
能量:0
我的帳號中心
問 學Bot 任何問題!
首頁&搜尋
最愛&收藏
所有課程
分享資源
帳號設定
關於學呀
線上募款
Python中的遞迴
編輯章節
EDU-MD
Google 教室
加至書籤
# 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] ``` 這樣的函數,雖然較剛才多了幾行,而且還多了列表的使用,但是在運算上卻能省下電腦極大的效能。
複製內容