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

上面的代码使用了参数来控制递归次数。只需使用你已经掌握的函数知识，按照程序的流程来理解就很简单。如果你有困难，可以回顾《Non-Programmer's Tutorial for Python 3/Advanced Functions Example》。

递归的实际应用

递归通常在计算机科学的高级课程中学习。递归通常用于解决可以拆分成多个较小、相似的子问题的复杂问题。递归并不是解决问题的必需方法。可以通过递归解决的问题，大多数情况下也可以使用循环来解决。此外，循环在很多情况下可能比递归函数更高效。递归函数需要比循环更多的内存和资源，因此在许多情况下递归效率较低。这种使用需求有时被称为“开销”。你可能会想：“既然递归不好，为什么还要用递归呢？我可以使用循环，反正我已经知道怎么写循环了，这样也能实现。”这种想法是可以理解的，但并不完全理想。在解决复杂问题时，递归函数有时更容易、更快，并且构建和编写代码会更简单。

想想这两个“规则”：

• 如果我现在可以不使用递归就解决问题，函数直接返回一个值。
• 如果我不能不使用递归就解决问题，函数会将问题缩小为更小、更相似的问题，然后调用自身来解决问题。

让我们用一个常见的数学概念——阶乘，来应用这个规则。如果你不熟悉数学中的阶乘，可以参考以下阅读内容：Factorials。

阶乘是一个数字 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()

在这个程序中，factorial 函数是一个递归函数，它不断调用自身，直到达到 num == 0 的条件，返回 1。