# Recursion 遞迴 + 又譯為**遞歸**，在數學與電腦科學中，是指在函數的定義中使用函數自身的方法。 + 程式設計中，函式不只能被其他函式呼叫，也能被自己呼叫；在一個函式中呼叫自己，即為遞迴函式 Recursive Function。 + 以下以費氏數列為例，它在 function 中呼叫自己，並就這樣一層一層呼叫以至可以找到值時，再一層一層回傳上來。    ``` python def fibonacci(n): if n == 0: return 0 elif n == 1: return 1 else: return fibonacci(n-1) + fibonacci(n-2) print(fibonacci(7)) # 13 ``` ## 介紹 在遞迴函式中： 在函式裡面中藉由呼叫自己去得到答案，並且是有一個階層的概念，會一路向下找，找到後再一層一層回傳進行指定運算。 當程式遇到 recursive call 時，必須保存當時的執行狀態，即 push 需要保存的內容到 stack memory 中，所以每多一層就多生成一個 **stack**，由於 stack 空間有限，若又不斷 push 的話就會爆掉，造成所謂的「Stack Overflow」，所以像 python 有限制 stack 上限是 3000。 `此 Stack Overflow 並不是程式設計師用的問答網站喔！雖然他們英文拼起來一樣:)` ## 解題應用 `Ｑ.小美確診了要吃藥，但她櫻桃小嘴，一次只能選擇吃一顆或是吃兩顆，試問今天有 n 顆藥丸，她可以有多少種不同吃法？` ( 可憐小美到底有幾顆藥丸要吃.... ``` n = 2 => Output = 2 1顆 1顆 2顆 n = 3 => Output = 3 1顆 1顆 1顆 1顆 2顆 2顆 1顆 ``` 範例解答如上 有興趣可以幫小美算算看   ## 以下解答 ``` n = 1 1 (n=1: 1種) n = 2 1 1 2 (n=2: 2種) n = 3 1 1 1 1 2 2 1 (n=3: 3種) n = 4 1 1 1 1 1 1 2 1 2 1 2 1 1 2 2 (n=4: 5種) n = 5 1 1 1 1 1 1 1 1 2 1 1 2 1 1 2 1 1 2 1 1 1 1 2 2 2 1 2 2 2 1 (n=5: 8種) ``` 其實可以發現，這存在著一種費氏數列的關係，F(5) = F (3) + F(4)，所以 F(n) = F(n-2) + F(n-1) 因此發燒的小美，就可以依照最上方費氏數列的遞迴邏輯，算出她總共有幾種不同的吃法了！   這邊提供另一種思路，一開始可以選擇吃一顆或吃兩顆 先吃一顆的話，剩下就還有 n-1 顆；先吃兩顆的話，剩下就還有 n-2 顆 所以如果今天有 n 顆，總共的吃法就是 *n-1的吃法* 與 *n-2的吃法* 的合 ``` python def eatMedicine(n): Arr = [0, 1, 2] for i in range(3, n+1): Arr.append(Arr[i-2] + Arr[i-1]) return Arr[n] print(eatMedicine(6)) # 13 ```   ## 參考資料： [維基百科 - 遞迴](https://zh.wikipedia.org/zh-tw/%E9%80%92%E5%BD%92) [【Day11】- 遞迴Recursion - iT 邦幫忙::一起幫忙解決難題](https://ithelp.ithome.com.tw/articles/10269528) [遞迴 (Recursive) 介紹與經典題型](https://kopu.chat/%E9%81%9E%E8%BF%B4-recursive-%E4%BB%8B%E7%B4%B9%E8%88%87%E7%B6%93%E5%85%B8%E9%A1%8C%E5%9E%8B/) [Python 初學第八講 — 遞迴](https://medium.com/ccclub/ccclub-python-for-beginners-tutorial-11ed5d300d3d) [70. Climbing Stairs [easy] (Python)](https://blog.csdn.net/coder_orz/article/details/51506414) Udemy - 資料結構與演算法 (JavaScript)