第三篇：递归

发表信息: by Creative Commons Licence

目录

什么是递归

把递归想象是在盒子里找钥匙

找盒子流程图如下：

找盒子代码如下：

前面流程图和代码，前一个都是循环，后一个是递归。

两种方法作用相同。递归只是让解决方案更清晰，并没有性能上的优势。实际上，在有些情况下，使用循环的性能更好。

由于递归函数自己调用自己，因此编写这样的函数时很容易出错，进而导致无限循环。

因此，编写递归函数时，必须告诉它何时停止递归。

递归函数：

基线条件（base case）：函数不再调用自己的条件

递归条件（recursive case）：函数调用自己的条件

比如我们给下面这段代码条件基线条件和递归条件

def countdown(x):
	print i
	countdown(i-1)

添加以后

def countdown(x):
	print i
	if i<= 0:  ==> 基线条件
		return 
	else:
		countdown(i-1)   ==> 递归条件

前面介绍了调用栈，递归函数也使用调用栈

举个例子，有助于理解调用栈和递归

def fact(x):
	if x==1:
		return 1
	else:
		return x*fact(x-1)

上述代码，执行fact(3)时整个调用栈的过程是：

注意，每个fact调用都有自己的x变量，在一个函数调用中不能访问另一个x变量

回到找盒子的例子里

使用循环时，创建了一个待查找的盒子堆，因此，始终知道还有那些盒子需要查找。

使用递归时，没有显性的创建盒子堆，但是实际上，栈已经偷偷替你完成了待查找盒子堆的创建。

使用栈虽然很方面，但也需要付出代价（前面写了）

这里针对递归再重复一遍

假如写了一个死循环的递归，导致栈不断的增加，由于每个程序可使用的调用栈空间都有限，程序使用完这些空间后，将因栈溢出而终止

[1] 算法图解 Aditya Bhargava (作者) 袁国忠 (译者)