重點

• 如何使用遞迴
• 遞迴跟迴圈的差異

為什麼要學遞迴

• 遞迴可以幫助我們用較簡單的方式處理複雜的問題
• 遞迴可以將困難的問題切割成數個相似的小問題，再用相同的方式去處理這些小問題
• 提供比迴圈更簡潔的處理方式

遞迴的使用方式

用法:

def 遞迴函式 ( ) :

    函式內程式碼

    if 遞迴終止的條件:

        return 與遞迴函式本身無關的資料

else :

    return 遞迴函式 ( )

• 函式在執行當中會不斷地自己呼叫自己
• 需設計一個明確的終止條件，否則函式永無止盡地自我呼叫

例1. 階乘

n !
= n * ( n - 1 ) !
= n * ( n - 1 ) ! * ( n - 2 ) !
……
= n * ( n - 1 ) ! * ( n - 2 ) ! * ……. 1 !

def fact(m):
    if m == 0 or m == 1:
        return 1
    else:
        return m * fact(m - 1)


num = 6
print(fact(num))
# 720

def fact(m):
    ans = 1
    for i in range(1, m + 1):
        ans *= i
    return ans


num = 6
print(fact(6))
# 720

遞迴及迴圈的比較

整理:

• 遞迴函式應注意
  • 如何呼叫函式本身
  • 設定終止條件

參考資料