遞迴 在

關於 遞迴

遞迴是一種在函式內部透過函式呼叫自己，來重複執行程式碼的方式。 會呼叫自己的函式稱為_遞迴_函式。 遞迴可以看成是另一種迴圈／疊代的方式。 就像迴圈一樣，會用布林運算式或True／False判斷來決定何時停止遞迴執行。

和迴圈不同，Python 中沒有終止條件的遞迴並不會無止盡地執行下去。 每次函式呼叫所用的值，都會放在 Python 翻譯員堆疊上各自所屬的框裡。 如果函式呼叫的總數佔用的空間超過堆疊的容量，就會導致錯誤。

迴圈與遞迴實作

迴圈和遞迴在「都是疊代」這件事上_感覺_很相似。 不過，無論從程式碼層面或實作層面來看，兩者_看起來_都不一樣。 迴圈可以在呼叫堆疊上的同一個框裡進行。 這通常是靠更新一個或多個變數的值，逐步為每次疊代維持狀態來達成。 這種實作很有效率，但看程式碼時可能會顯得有點雜亂。

遞迴則不更新_變數狀態_，而是把_更新後的值_直接當作引數，傳給同一個函式的下一次呼叫（疊代）。 這能讓函式主體更清爽，也能讓每次更新是怎麼發生的更清楚。 不過，它的效率也比較差，因為每次呼叫同一個函式都會在堆疊上多加一個框。

為什麼要用遞迴，又為什麼不該用？

如果有可能造成堆疊錯誤或溢位，那為什麼還會有人用遞迴策略來解決問題？ 可讀性、可追蹤性，以及意圖。 有些情況下，用遞迴表達的解法會比用迴圈表達來得更好讀，也更容易推敲。 也可能會有一些程式上的限制，涉及資料的使用／改動、複雜度的管理、責任的委派，或工作量的安排。

適合用遞迴處理的問題，包括複雜但重複、而且會隨時間變小的問題，特別是分治法演算法和累積演算法。 不過，由於 Python 對堆疊上能容納多少個框有所限制，並不是所有問題都能從完全遞迴的策略中獲益。 比較不適合用遞迴的問題，包括處於穩定狀態、但需要重複固定次數循環的問題、需要非同步執行的問題，以及需要大量疊代的情況。

迴圈與遞迴策略：Indira 的煩惱

Indira 的社會安全補助款每個月會自動存入她的銀行帳戶，日期是每個月的**第二個星期三**。 Indira 擔心自己沒辦法把支票簿記帳平衡。 她怕自己在錢還沒存入前就開了支票。 她請孫女 Adya 幫她列出一份錢會出現在帳戶裡的日期清單。

Adya 才剛開始學寫 Python 程式，她根據自己最初的想法寫了一個程式。 她想回傳一份存款日期的list，這樣就能印出來。 她想寫一個對_任何年份_都適用的函式。 為了以防時程改變（或是其他親戚也想請 Adya 幫他們計算存款時程），她決定函式需要多一個_星期幾_的參數。 最後，Adya 決定函式還需要一個參數，指出那是當月的_第幾個_星期幾：第一個、第二個等等。 基於這些需求，她決定使用從datetime匯入的date類別。 把這些全部兜在一起，Adya 寫出了：

from datetime import date


def paydates_for_year(year, weekday, ordinal):
    """Returns a list of the matching weekday dates.
    
    Arguments:
        year (int): The year (e.g. 2022).
        weekday (int): The weekday number (e.g. 3 for Wednesday).
        ordinal (int): Which weekday of the month (e.g. 2 for the second day).
    
    Returns:
        output (list): Matching weekday dates.
    """
    
    output = []

    for month in range(1, 13):
        for day_num in range(1, 8):
            if date(year, month, day_num).isoweekday() == weekday:
                output.append(date(year, month, day_num + (ordinal - 1) * 7))
                break
    return output

# find the second Wednesday of the month for all the months in 2022
print(paydates_for_year(2022, 3, 2))

這第一個版本可行，但 Adya 想知道自己能不能重構程式碼，用更少的行數和更少的巢狀迴圈。 她也讀到過，盡量減少改動狀態是件好事，所以她想看看能不能避免改動output、month和day_num這些變數。

她也知道遞迴，並想著要怎麼把程式改成用遞迴的方式。 她在迴圈函式中建立並改動的變數，可以改用引數傳入。 與其改動函式_內部_的變數，她可以把_更新後的值當作引數_傳給下一次函式呼叫。 抱持著這些想法，她寫出了這個遞迴版本：

from datetime import date


def paydates_for_year_rec(year, weekday, ordinal, month, day_num, output):
    """Returns a list of the matching weekday dates
    
    Arguments:
        year (int): The year (e.g. 2022).
        weekday (int): The weekday number (e.g. 3 for Wednesday).
        ordinal (int): Which weekday of the month (e.g. 2 for the second day).
        month (int): The month number currently being processed.
        day_num (int): The day number of the month currently being processed.
    
    Returns:
        output (list): Matching weekday dates.
    """
    
    if month == 13:
        return output
        
    if date(year, month, day_num).isoweekday() == weekday:
        return paydates_for_year_rec(
                 year, weekday, ordinal, month + 1, 1, output
                 + [date(year, month, day_num + (ordinal - 1) * 7)]
                 )
    
    return paydates_for_year_rec(year, weekday, ordinal, month, day_num + 1, output)

# find the second Wednesday of the month for all the months in 2022
print(paydates_for_year_rec(2022, 3, 2, 1, 1, []))

Adya 很開心，因為沒有巢狀迴圈了、沒有被改動的狀態，程式碼還少了 2 行！

她有點擔心遞迴版本比迴圈版本用了更多步驟，因此「效能」比較差。 但用遞迴重寫這個問題，確實幫她擺脫了醜陋的巢狀迴圈（一種效能隱憂）、大量的狀態改動，以及複雜條件邏輯帶來的困惑。 她也覺得這樣更「好讀」，她確信等自己休息一陣子再回來看這段程式碼時，能更輕鬆地讀過去並想起它在做什麼。

未來，Adya 也許會試著先用遞迴來處理問題。 她可能會發現，當巢狀、改動和複雜度都降到最低時，一開始用清楚的步驟走過問題會比較容易。 釐清基本邏輯之後，她就能專心把最初的遞迴步驟最佳化成效能更好的迴圈做法。

再更久以後，等她學到 tuples 時，Adya 可以考慮進一步「最佳化」的做法，例如使用搭配 Calendar.itermonthdates 的list comprehension，或對某些值做記憶化。

遞迴的變化：尾端呼叫

尾端呼叫是指函式的最後一個敘述只呼叫自己，不做其他事。 下面這個例子不是尾端呼叫，因為函式把呼叫自己得到的結果加上了 1：

def print_increment(step, max_value):
    if step > max_value:
        return 1
    print(f'The step is {step}')
    return 1 + print_increment(step + 1, max_value)


def main():
    retval = print_increment(1, 2)
    print(f'retval is {retval} after recursion')

if __name__ == "__main__":
    main()

它會印出：

The step is 1
The step is 2
retval is 3 after recursion

要把這段改成尾端呼叫，就把retval變成print_increment的一個參數。

def print_increment(step, max_value, retval):
    if step > max_value:
        return retval
    print(f'The step is {step}')
    return print_increment(step + 1, max_value, retval + 1)


def main():
    retval = print_increment(1, 2, 1)
    print(f'retval is {retval} after recursion')

if __name__ == "__main__":
    main()

你可能會覺得尾端呼叫比不是尾端呼叫的遞迴呼叫更容易推敲。 不過，使用遞迴時，永遠要記得確認疊代次數不會多到讓堆疊溢位。

Python 中的遞迴上限

有些語言能最佳化尾端呼叫，讓每次遞迴呼叫重複使用函式第一次呼叫的堆疊框（類似迴圈重複使用同一個框的方式），而不是在堆疊上再加一個框。 Python 不是這類語言。 為了防止堆疊溢位，Python 有一個遞迴上限，預設是一千個框。 當翻譯員偵測到遞迴次數超過上限時，會引發 RecursionError 例外。 可以用 sys.setrecursionlimit 方法提高遞迴上限，但這麼做會有執行時期分段錯誤的風險，可能讓程式崩潰，甚至可能讓作業系統一起崩潰。

資源

想進一步了解 Python 中遞迴的用法，可以從這裡開始

• python-programming: recursion
• Real Python: python-recursion
• Real Python: python-thinking-recursively