第5章 递归电子课件

第5章递归本章讲解递归。要求理解递归概念，掌握建递归模型，灵活应用递归解决复杂问题。吃货办席，要把大块肉弄熟，但锅儿只有那么大，一次性装不下怎么办？难不倒吃货！吃货把大块肉分成很多小块肉，再用小竹篮打包，批量放入锅里蒸烤，直到所有肉蒸烤完。原来大问题分解为若干个小问题，所有小问题解决了，大问题也就解决了，这是递归思想。提纲5.1递归概念和原理

5.2递归模型5.3递归算法应用5.4递归学习总结5.1递归概念和原理1.定义在定义一个过程或函数时出现调用本过程或本函数的成分，称为递归。5.1递归概念和原理举例：小口瓶子装了大半瓶碎石头，要将所有石头倒出来，试了几次都堵在瓶口了。慢慢倾斜慢慢倒，一颗一颗倒，最终全部倒出来了。在这个例子中，全部石头倒出来是大问题，倒一颗石头是与大问题相似的小问题，所有小问题解决了，大问题也就解决了，这就是一种递归思想。5.1递归概念和原理递归思想的本质是将1个复杂的大问题，通过层层分解，分解为若干个简单的又与大问题相似的小问题，所有小问题解决了，大问题也就解决了。5.1递归概念和原理2.工作栈递归算法在系统内部的执行是通过1个工作栈来实现的，工作栈工作原理：执行开始时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址。每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址进栈。每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部变量恢复为调用前的值，然后转向返回地址指定的位置继续执行。5.1递归概念和原理递归过程实质上分为分解过程和返回过程，如图5.1所示求5！。5.1递归概念和原理【算法5.1】简单的递归求和。思路:利用递归调用完成求和。代码见算法5.15.1递归概念和原理3.应用条件满足下面3个条件可以运用递归算法解决问题。（1）大问题可以转化为若干个小问题来求解，而这些小问题的求解

方法与大问题相似，只是在数量规模上不同。（2）递归调用的次数必须是有限的。（3）必须有结束递归的条件来终止递归。5.1递归概念和原理4.应用场景递归算法的应用，往往有下面3种情形可应用递归算法解决问题。（1）定义是递归的。如许多数学公式、数列等的定义是递归的。例如，求n!和Fibonacci（斐波那契）数列等。（2）数据结构是递归的。如单链表结点结构，其内指针域又是1个单链表结点。（3）求解问题的方法是递归的。如求解汉诺塔问题，多级目录查找文件问题，等。5.2递归模型

5.2递归模型5.2递归模型【思考与练习5.2】下面问题的求解，请写出递归模型。求n！求数组a[0...n-1]中的最大值。求Fibonacci数列。单链表的遍历。5.2递归模型

5.3递归算法应用【例5.1】创建并初始化1个不带头结点的单链表，分别对该单链表正向和反向输出其所有结点。思路：（1）设f(p)为正向输出单链表所有结点（a1...an），是大问题，显然f(p.next)输出（a2...an）是小问题，当p为null时不做任何事。5.3递归算法应用

5.3递归算法应用思路：（2）设g(p)为反向输出单链表所有结点（an...a1），是大问题，显然f(p.next)输出（an...a2）是小问题，当p为null时不做任何事。与正向输出不同的是，先让p移动，再输出p结点。5.3递归算法应用

5.3递归算法应用【进一步思考】正反向遍历顺序表，也可以用递归算法实现吗，为什么？答：可以。同例5.1算法，大问题可以分解为相似的问题，如a[0...n-1]是大问题，a[1...n-1]/a[0...n-2]是小问题。5.3递归算法应用

5.3递归算法应用【进一步思考】在分析递归和非递归算法时空复杂度时，有什么不同的考虑？答：在分析非递归算法时，主要看时间频度与问题规模之间的关系，算法的主要语句执行的次数来确定之，辅助变量与问题规模是否相关；在分析递归算法时，要考虑嵌套调用次数以及递归栈所需空间，即要计算时间和空间的递推式，如例5.2算法中通过时间和空间递推式计算出递归算法的时间和空间复杂度。5.3递归算法应用

5.3递归算法应用

5.3递归算法应用【进一步思考】若用非递归算法产生螺旋矩阵，实现思路又是什么？答：循环嵌套，对二维数组遍历赋值，赋值是需根据当前行考虑数学计算。5.4递归学习总结递归算法总可以转换为用栈结构实现的算法，这是由递归工作原理推出的。递归算法使得代码简洁、优雅，代价往往是时空开销更大。时空复杂度分析，对于非递归算法是定长的，对于递归算法是变长的。递归算法的时间复杂度求解有3种常见的方法：递推式，master定理，递归树。读者掌握其中1种如递推式求解即可。递归算法的时间复杂度=每1次递归的时间复杂度*递归次数；递归算法的空间复杂度=每1次递归的空间复杂度*递归深度。递归算法空间复杂