python递归
栏目分类：Python教程 发布日期：2020-01-18 浏览次数：次
递归
我们上一节学习了函数的嵌套，可以在一个函数里调用另外一个函数，但是能不能在函数里调用自己呢？
结果发现程序刚开始可以正常运行，但是在输出无数次的“test”后，还是报错了，这是因为函数虽然可以自己调用自己，但是由于没有设置结束条件，所以它会不停的调用自己，就像进入一个无底洞一样，直到内存占满，程序才会报错，所以当需要函数自己调用自己的时候，一定要给它这个无底洞设置一个底，也就是告诉它程序什么时候结束。下面修改代码如下：
输出结果：
test: 3
test: 2
test: 1
test: 0
这里的函数在每次调用自身的时候，传递进来的参数都会执行一次减一操作，当它到0的时候，我们使用return结束函数，这就是该函数的界限，有了它，函数在调用自己的过程中就会找到出口，程序也就可以正常执行了。整个执行过程如下图所示。像这样自己调用自己的函数，我们称之为递归函数。
综上所述，一个递归函数必须包括终止条件和递归部分。
输出结果：
24
在阶乘运算中规定0的阶乘是1，1的阶乘也是1，所以函数运行的界限可视为n为0或1，设置好界限后就可以依次递减地调用函数自身了，直到到达界限，函数结束。请读者自行推断此程序运行规律。
例2：python求斐波那契数列的第n项。
斐波那契数列：从第三个数开始，每一个数都是前面两个数的和。
1，1，2，3，5，8，13，21.......
输出结果：
21
由于第1项和第2项都是1，所以终止条件设为当n为1或者2时，返回值为1.后面每一项的值都为前两项相加，所以返回值为第n-1项和n-2项之和。输出第8项的值为21.
本小节中算法和栈的概念请参考数据结构和算法教程，虽然使用的语言不同，但是思想是完全一样的。
我们上一节学习了函数的嵌套，可以在一个函数里调用另外一个函数，但是能不能在函数里调用自己呢？
1.递归的概念
请实验下述代码：结果发现程序刚开始可以正常运行，但是在输出无数次的“test”后，还是报错了，这是因为函数虽然可以自己调用自己，但是由于没有设置结束条件，所以它会不停的调用自己，就像进入一个无底洞一样，直到内存占满，程序才会报错，所以当需要函数自己调用自己的时候，一定要给它这个无底洞设置一个底，也就是告诉它程序什么时候结束。下面修改代码如下：
输出结果：
test: 3
test: 2
test: 1
test: 0
这里的函数在每次调用自身的时候，传递进来的参数都会执行一次减一操作，当它到0的时候，我们使用return结束函数，这就是该函数的界限，有了它，函数在调用自己的过程中就会找到出口，程序也就可以正常执行了。整个执行过程如下图所示。像这样自己调用自己的函数，我们称之为递归函数。
综上所述，一个递归函数必须包括终止条件和递归部分。
2.递归的应用
例1：求n的阶乘，即n*(n-1)*(n-2)*(n-3)......*1输出结果：
24
在阶乘运算中规定0的阶乘是1，1的阶乘也是1，所以函数运行的界限可视为n为0或1，设置好界限后就可以依次递减地调用函数自身了，直到到达界限，函数结束。请读者自行推断此程序运行规律。
例2：python求斐波那契数列的第n项。
斐波那契数列：从第三个数开始，每一个数都是前面两个数的和。
1，1，2，3，5，8，13，21.......
输出结果：
21
由于第1项和第2项都是1，所以终止条件设为当n为1或者2时，返回值为1.后面每一项的值都为前两项相加，所以返回值为第n-1项和n-2项之和。输出第8项的值为21.
3.使用递归的利弊
递归是一种常见的算法，对于许多问题来说，只要我们可以找到递归方程和终止条件，那么就可以使用递归来解决问题。从上面两个例子可以看出，使用递归可以大大减少代码量，在工作中，递归函数给程序员带来了很大的便捷——使用很简短的代码去实现一个复杂的问题，但是却会给计算机的处理器和内存带来很大的麻烦——处理器需要反复调用函数，每次调用，在内存中都要建立函数栈帧，然后达到终止条件后，再一层层地退栈，对于系统来说，这是一笔很大的开销，会是程序运行效率大打折扣。所以再追求效率的时候，我们不得不舍弃这样的方法去写代码。本小节中算法和栈的概念请参考数据结构和算法教程，虽然使用的语言不同，但是思想是完全一样的。
本文由IT教学网整理发布，转载请注明出处：http://www.itjx.com/jiaocheng/Python/2020/0118/524.html
