Python 3 非程式設計師教程/遞迴

遞迴

在 Python 中，遞迴函式是指呼叫自身的函式。

遞迴介紹

到目前為止，我們在 Python 中已經看到了呼叫其他函式的函式。但是，函式也可以呼叫自身。讓我們看一個簡單的例子。

# Program by Mitchell Aikens
# No Copyright
# 2010

num = 0

def main():
    counter(num)

def counter(num):
    print(num)
    num += 1
    counter(num)

main()

如果在 IDLE 中執行這個程式，它將永遠執行下去。停止迴圈的唯一方法是透過按鍵盤上的 Ctrl + C 中斷執行。這是一個無限遞迴的例子。(一些使用者報告了當前 IDLE 系統中的一個故障，導致 Ctrl + C 引發的異常也開始迴圈。如果發生這種情況，請按 Ctrl + F6，IDLE shell 應該會重新啟動。)

可以說，遞迴只是實現與 while 迴圈相同目的的另一種方式。在某些情況下，這絕對是正確的。然而，遞迴還有其他非常有效的用途，而 while 迴圈或 for 迴圈可能不是最佳選擇。

遞迴可以像迴圈一樣被控制。讓我們來看一個受控迴圈的例子。

# Program by Mitchell Aikens
# No copyright
# 2012
def main():
    loopnum = int(input("How many times would you like to loop?\n"))
    counter = 1
    recurr(loopnum,counter)

def recurr(loopnum,counter):
    if loopnum > 0:
        print("This is loop iteration",counter)
        recurr(loopnum - 1,counter + 1)
    else:
        print("The loop is complete.")

main()

以上使用了引數/引數來控制遞迴的次數。只需使用你已經瞭解的關於函式的知識，並遵循程式的流程即可。它很容易理解。如果你遇到困難，請參考 Python 3 非程式設計師教程/高階函式示例。

遞迴的實際應用

通常，遞迴是在高階計算機科學水平上學習的。遞迴通常用於解決可以分解成更小、相同問題（子問題）的複雜問題。遞迴不是解決問題的必要條件。可以使用遞迴解決的問題，大多數情況下可以使用迴圈解決。此外，迴圈可能比遞迴函式更有效。遞迴函式比迴圈需要更多記憶體和資源，這使得它們在許多情況下效率較低。這種使用要求有時被稱為開銷。你可能會想：“好吧，為什麼還要使用遞迴呢？我只要用迴圈就可以了。我已經知道如何迴圈了，這要多做很多工作。”這種想法是可以理解的，但並不完全理想。在解決複雜問題時，遞迴函式有時更容易、更快、更簡單地構建和編碼。

想想這兩個“規則”

• 如果現在可以不使用遞迴解決問題，該函式只需返回一個值。
• 如果現在不能不使用遞迴解決問題，該函式將問題簡化為更小、類似的問題，並呼叫自身來解決該問題。

讓我們使用常見的數學概念階乘來應用它。如果你不熟悉數學中的階乘，請參考以下閱讀材料。階乘

數字n的階乘用n!表示。

以下是一些階乘的基本規則。

如果 n = 0 則 n! = 1 如果 n > 0 則 n! = 1 x 2 x 3 x ... x n

例如，讓我們看看數字 9 的階乘。

9! = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9

讓我們看一個程式，該程式透過遞迴方法計算使用者輸入的任何數字的階乘。

def main():
    num = int(input("Please enter a non-negative integer.\n"))
    fact = factorial(num)
    print("The factorial of",num,"is",fact)

def factorial(num):
    if num == 0:
        return  1
    else:
        return num * factorial(num - 1)

main()