# Python 遞迴

**函式的遞迴就是函式使用自己本身**

舉個例子:

def past( a ):
    if a == 1:
        return 1
    return a * past ( a - 1 )

這是「階乘」的遞迴函式表示法，階乘的話舉個例子:

5! = 5 * 4 * 3 * 2 * 1

而其中我們輸入是5

**第一步:5!是多少**
5! = 5 * (4!)
這個時候*問題簡化為4!是多少*，如果知道4!是多少
就可以把4! * 5 就是答案了
下一步求4!是多少

**第二步:4!是多少**
4! = 4 * (3!)
這個時候*問題簡化為3!是多少*，如果知道4!是多少
就可以把3! * 4 就是答案了
下一步求3!是多少

**第三步:3!是多少**
3! = 3 * (2!)
這個時候*問題簡化為2!是多少*，如果知道2!是多少
就可以把2! * 3 就是答案了
下一步求2!是多少

**第四步:2!是多少**
2! = 2 * (1!)
這個時候*問題簡化為1!是多少*，如果知道1!是多少
就可以把1! * 2 就是答案了
下一步求1!是多少

**第五步:1!是多少**
我們知道1! = 1
函式輸出 1
下一步回推

**第六步:5!是多少**
我們知道1! = 1
那麼回推
2! = 2
3! = 6
4! = 24
5! = 120
得到解答:120
最後會是輸出120

**先搞懂上面階乘為甚麼會是這樣，先搞懂，才能自己寫**

# base case

所謂的 base case，就是*告訴函式甚麼時候要停*，如果沒有告訴函式甚麼條件下要停下來，可能會一直呼叫自己叫到電腦出現錯誤為止 = =

base case通常長這樣

if 判斷式:
    return 確定值

以上方舉過的階乘為例
因為可以確定1! = 1，所以 1! 就是base case
**遞迴函式會不斷呼叫自己，直到出現base case為止**
應該可以說全部的遞迴函式都是利用base case往上進行計算

# 基本架構

def 函式名稱(輸入):
    if base case成立:
        程式碼
        return 值
    else:
        程式碼
        return 函式名稱(輸入)

# 為甚麼要用遞迴?
執行遞迴函式相當吃記憶體而且執行效率不高，但在一些情況下，反而是遞迴較為直觀，像是上方的階乘就是其中一個

# 功課
共有兩個，甚麼時候交都行
1. 請不要查網路，第0項為0，第1項為1，輸入一正整數 N，求出斐波納契數列的第N項(斐波納契數列的每一項都是前兩項之和，這個例子用遞迴比迴圈好理解)
2. 請不要查網路，將最大公因數函式寫成遞迴的寫法