使用 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)