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頻道來索取