Python基础教程6.6 递归

6.6 递归

前面深入介绍了如何创建和调用函数。你知道，函数可调用其他函数，但可能让你感到惊讶的是，函数还可调用自己。

如果你以前没有遇到这种情况，可能想知道递归是什么意思。 简单地说，递归意味着引用（这里是调用）自身。下面是一个常见的递归定义（但必须承认，这种定义很愚蠢）：

递归[名词]：参见“递归”。

如果你在网上搜索“递归”，将看到类似的定义。

递归式定义（包括递归式函数定义）引用了当前定义的术语。递归可能难以理解，也可能非常简单，这取决于你对它的熟悉程度。要更深入地认识递归，可能应该参阅优秀的计算机教材，但尝试Python解释器也大有裨益。

一般而言，你不想要递归式定义（像前面的“递归”那样），因为这毫无意义：你查找“递归”，它告诉你去查找“递归”，如此这般没完没了。下面是一个递归式函数定义：

def recursion():

return recursion()

这个定义显然什么都没有做，与刚才的“递归”定义一样傻。如果你运行它，结果将如何呢？你将发现运行一段时间后，这个程序崩溃了（引发异常）。从理论上说，这个程序将不断运行下

去，但每次调用函数时，都将消耗一些内存。因此函数调用次数达到一定的程度（且之前的函数调用未返回）后，将耗尽所有的内存空间，导致程序终止并显示错误消息“超过最大递归深度”。

这个函数中的递归称为无穷递归（就像以while True打头且不包含break和return语句的循环被称为无限循环一样），因为它从理论上说永远不会结束。你想要的是能对你有所帮助的递归函数，这样的递归函数通常包含下面两部分

基线条件（针对最小的问题）：满足这种条件时函数将直接返回一个值。

递归条件：包含一个或多个调用，这些调用旨在解决问题的一部分。

这里的关键是，通过将问题分解为较小的部分，可避免递归没完没了，因为问题终将被分解成基线条件可以解决的最小问题。

那么如何让函数调用自身呢？这没有看起来那么难懂。前面说过，每次调用函数时，都将为此创建一个新的命名空间。这意味着函数调用自身时，是两个不同的函数［更准确地说，是不同版本（即命名空间不同）的同一个函数］在交流。你可将此视为两个属于相同物种的动物在彼此交流。