262 递归算法2 – 大师码

< 1 min read

递归算法2 #

在使用递归算法之前，我们需要首先明确递归函数的定义，这一点和普通函数定义一样，包括递归函数的功能、参数、返回值都要有明确的定义。这些都是根据解决问题的需要由自己定义的。
我们以求解从1累加到n的和为例，首先定义mysum(n)函数，该函数的功能就是返回1~n累加的和。

def mysum(n):#mysum函数功能：返回1~n累加和，参数为n
	pass

递归问题的拆解是递归算法中最重要的一个环节，最基本的思想是将一个规模较大的问题，逐渐拆解成规模较小的问题，直到被拆解的问题能够十分容易被解决。

在上例中我们很容易就可以想到，可以将求1~n的和，拆解成先求1~(n-1)的和再加上n,即在数学上有mysum(n)=mysum(n-1)+n的等式成立，求1~n-1的和同样可以使用上述的方法进行拆解。程序表示如下：

def mysum(n):
	sum= mysum(n-1)+n#递归函数地拆解
	return sum

调用上述递归函数mysum(n)时候会出现递归深度溢出的问题，可以想一想为什么？一个简单的解释就是该递归函数没有出口，实际上在执行mysum(n)函数第二句:sum= mysum(n-1)+n时，函数会被一直拆解下去，陷入一个死循环，导致递归没有回溯的过程。

任何一个有意义的递归函数都要有自身的边界条件，也即是递归函数的出口。上述递归函数mysum(n)逐步拆解成mysum(1)时，返回值显然是1，可以将当n等于1，作为递归的出口

def mysum(n):
	if n==1:
		return 1 #递归的出口
	sum= mysum(n-1)+n#递归的拆解
	return sum

掌握递归的三要素

理解常见问题的递归解答思路