Alg2.1. 遞迴

對於遞迴的概念每個人的喜好都有所不同，例如：迴圈對於程式本身是有效益的，遞迴則是對程式設計師是有效益的，要使用那一個方式則端看那一種情況對使用者是更重要的。

Loops may achieve a performance gain for your program. Recursion may achieve a performance gain for your programmer. Choose which is more important in your situation! -- Leigh Caldwell

如同一個玩偶嵌套另一個玩偶的俄羅斯娃娃，若對應到遞迴則是一個函數會自已呼叫函數自已。此外，在使用遞迴函數時還需要知道什麼時候要繼續遞迴，或是什麼時候要停止遞迴及回傳結果。所以，遞迴函數內通常會有兩種情況：函數持續遞迴的遞迴情況 (recursive case) 及停止遞迴的基本情況 (basic case)。

def recusion(x):
    if 條件式:
        # 基本情況
        return value
    else:
        # 遞迴情況
        return recusion(計算式)

• 參考檔案：fact.py

# 定義函數
def fact(x):
    if x == 1:
        print('f(x = {0})'.format(x))
        print('Basic case: x = 1, return 1')
        print()
        print('----')
        print()

        return 1                                        # x == 1 時為基本情況，則回傳 1
    else:
        print('f(x = {0})'.format(x))
        print('Recusive case: fact({0} - 1)'.format(x))
        print()

        fact_result = fact(x - 1)                       # x != 1 時為遞迴情況，則呼叫函數本身

        print('f(x = {0})'.format(x))                   # 此處為遞迴返迴處，回傳 x * f(x - 1)
        print('Return: {0} * fact({0} - 1) = {1}'.format(x, fact_result))
        print()
        return x * fact_result


# 呼叫函數
print(fact(3))


# 執行結果
f(x = 3)
Recusive case: fact(3 - 1)

f(x = 2)
Recusive case: fact(2 - 1)

f(x = 1)
Basic case: x = 1, return 1

----

f(x = 2)
Return: 2 * fact(2 - 1) = 1

f(x = 3)
Return: 3 * fact(3 - 1) = 2

6

參考資料

• Recursion or Iteration?
• 寫程式前就該懂的演算法, 第三章, Aditya Y.Bhargava著, 張書華譯, 松崗, ♥️