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()

來做查詢