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()