递归算法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
小结
掌握递归的三要素
理解常见问题的递归解答思路
习题
- 在mysum(n)的递归函数中，我们将递归的出口放在了递归问题拆解的前面，想一想为什么？能够交换位置吗？
- 使用循环迭代的方式实现mysum(n)的功能，并尽量找出它与递归方式的不同