Python基礎: 遞迴 recursive

首頁 >> Research >> 程式設計 >> Python基礎: 遞迴 recursive

之前簡單介紹過函式的入門
可以透過函式來執行一些重複的步驟,
今天的主題也與函式有些關聯

Python基礎: 遞迴 recursive

何謂遞迴

在解決問題的時候,
將此問題拆解為多個小問題,
再以同個函式求得這些小問題的解答,
來獲取這個問題的解答;
遞迴的概念就相當於這種做法,
而在函式執行過程中會呼叫自己本身的,
也將其稱為遞迴函式

階乘 factorial

階乘的定義為:
1 * 2 * 3 …….*(n-1)*n
將其寫為  n!
也就是從 1 開始一直連乘直到 n 為止,
可將這個 n! 寫為
[  1 * 2 * 3 …….*(n-1)  ] *n   也就是 f(n-1)*n
這樣比較容易理解
在遞迴的概念中,
將 1 做為遞迴函式的結束;
範例程式求得 ans = 5! = 120

費氏數列 fibonacci

另一個有名的例子就是費氏數列,
一個數列的某個值,
等於它的前兩項的和,
這個數列稱之為費氏數列
也就是
f(n) = f(n-1) + f(n-2)
n必須大於等於 2  ,
故 f(0) 與 f(1) 直接就 return 值不做遞迴呼叫

結論

除了上述的兩個例子以外,
最大公因數也能透過遞迴的方式來求得;
使用遞迴能讓程式更為簡短與簡潔,
不過由於需要等待遞迴函式求得最終解答,
相對的會花費比較多的時間,
而且為了儲存遞迴過程中的中間解也需要花費較多的記憶體;
為了避免無窮的遞迴下去,
Python 對遞迴的次數有限制,
可透過

sys.getrecursionlimit()

來做查詢

當然範例程式會將其放在 GitHub 上面,

需要的人可訂閱本站的 YouTube頻道來索取



================================
分享與讚美,是我們繼續打拼的原動力.
若文章對您有幫助,望請不吝按讚或分享.
或者對影片有興趣可以訂閱頻道接收通知
================================
YouTube 頻道
FB 粉絲專頁
================================

guangyaw

重點主題: 程式設計: Python , Django,Android 工具與軟體: Open edX,Linux工具,Blender教學 分享各地美景與產品使用心得,遊戲實況,甚至影視戲劇等, 您的訂閱就是頻道成長的原動力。 YouTube 頻道: https://youtube.com/xyawli

You may also like...

發表迴響