使用 Linkbot 學習 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 教程/高階函式示例。

遞迴的實際應用

通常，遞迴是在高階計算機科學課程中學習的。遞迴通常用於解決複雜問題，這些問題可以分解成更小的、相同的問題。遞迴不是解決問題的必要條件。可以用遞迴解決的問題，很可能可以用迴圈解決。而且，迴圈可能比遞迴函式更有效率。遞迴函式比迴圈需要更多的記憶體和資源，這使得它們在很多情況下效率較低。這種使用需求有時被稱為開銷。你可能會想，“為什麼要 bother with recursion。我只需要用迴圈。我已經知道如何迴圈了，而且這比遞迴要容易得多。”這種想法是可以理解的，但並不完全理想。在解決複雜問題時，遞迴函式有時更容易、更快、更簡單地構建和編碼。

請記住這兩個“規則”

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

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

一個數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()

遞迴在生成器這種高階主題中也很有用。要生成序列 1,2,1,3,1,2,1,4,1,2... 我們需要以下程式碼

def crazy(min_):
    yield min_
    g=crazy(min_+1)
    while True:
        yield next(g)
        yield min_

i=crazy(1)

要獲取下一個元素，你需要呼叫 next(i)