第5章 递归
本章讲解递归。要求理解递归概念，掌握建递归模型，灵活应用递归解决复杂问题。
吃货办席，要把大块肉弄熟，但锅儿
只有那么大，一次性装不下怎么办？难
不倒吃货！吃货把大块肉分成很多小块
肉，再用小竹篮打包，批量放入锅里蒸
烤，直到所有肉蒸烤完。原来大问题分
解为若干个小问题，所有小问题解决了，
大问题也就解决了，这是递归思想。
提纲
• 递归概念和原理
• 递归模型
• 递归算法应用
• 递归学习总结
递归概念和原理
•1.定义
•在定义一个过程或函数时出现调用本过程或
本函数的成分，称为递归。
递归概念和原理
举例：小口瓶子装了大半瓶碎石头，要将所有石头倒出来，
试了几次都堵在瓶口了。慢慢倾斜慢慢倒，一颗一颗倒，
最终全部倒出来了。在这个例子中，全部石头倒出来是大
问题，倒一颗石头是与大问题相似的小问题，所有小问题
解决了，大问题也就解决了，这就是一种递归思想。
递归概念和原理
•递归思想的本质是将1个复杂的大问题，通
过层层分解，分解为若干个简单的又与大问
题相似的小问题，所有小问题解决了，大问
题也就解决了。
递归概念和原理
2.工作栈
• 递归算法在系统内部的执行是通过1个工作栈来实现的，工作栈工作原理：
1.执行开始时，首先为递归调用建立一个工作栈，其结构包括值参、局部变
量和返回地址。
2.每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用
后的返回地址进栈。
3.每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部变量恢复为
调用前的值，然后转向返回地址指定的位置继续执行。
递归概念和原理
• 递归过程实质上分为分解过程和返回过程，如图所示求5！。
递归概念和原理
•【算法】简单的递归求和。
• 思路:利用递归调用完成求和。
代码见算法
递归概念和原理
3.应用条件
• 满足下面3个条件可以运用递归算法解决问题。
（1）大问题可以转化为若干个小问题来求解，而这些小问题的求解
方法与大问题相似，只是在数量规模上不同。
（2）递归调用的次数必须是有限的。
（3）必须有结束递归的条件来终止递归。
递归概念和原理
4.应用场景
• 递归算法的应用，往往有下面3种情形可应用递归算法解决问题。
（1）定义是递归的。如许多数学公式、数列等的定义是递归的。例如，
求n!和Fibonacci（斐波那契）数列等。
（2）数据结构是递归的。如单链表结点结构，其内指针域又是1个单链
表结点。
（3）求解问题的方法是递归的。如求解汉诺塔问题，多级目录查找文件
问题，等。
递归模型
递归模型
递归模型
•【思考与练习】
下面问题的求解，请写出递归模型。
1.求n！
2.求数组a[0...n-1]中的最大值。
3.求Fibonacci数列。
4.单链表的遍历。
递归模型
递归算法应用
• 【例】创建并初始化1个不带头结点的单链表，分别对该单
链表正向和反向输出其所有结点。
• 思路：（1）设f(p)为正向输出单链表所有结点（a1...an），
是大问题，显然f()输出（a2...an）是小问题，当p为
null时不做任何事。
递归算法应用
递归算法应用
• 思路：（2）设g(p)为反向输出单链表所有结点（an...a1），是
大问题，显然f()输出（an...a2）是小问题，当p为null
时不做任何事。与正向输出不同的是，先让p移动，再输出p结
点。
递归算法应用
递归算法应用
• 【进一步思考】正反向遍历顺序表，也可以用递归算法实现吗，
为什么？
•答：可以。同例算法，大问题可以分解为相似的问题，如
a[0...n-1]是大问题，a[1...n-1]/a[0...n-2]是小问题。
递归算法应用
递归算法应用
• 【进一步思考】在分析递归和非递归算法时空复杂度时，有什
么不同的考虑？
• 答：在分析非递归算法时，主要看时间频度与问题规模之间的
关系，算法的主要语句执行的次数来确定之，辅助变量与问题规
模是否相关；在分析递归算法时，要考虑嵌套调用次数以及递归
栈所需空间，即要计算时间和空间的递推式，如例算法中通
过时间和空间递推式计算出递归算法的时间和空间复杂度。
递归算法应用
递归算法应用
递归算法应用
• 【进一步思考】若用非递归算法产生螺旋矩阵，实现思路又是
什么？
• 答：循环嵌套，对二维数组遍历赋值，赋值是需根据当前行考
虑数学计算。
递归学习总结
递归算法总可以转换为用栈结构实现的算法，这是由递归工作原理推出的。
递归算法使得代码简洁、优雅，代价往往是时空开销更大。
时空复杂度分析，对于非递归算法是定长的，对于递归算法是变长的。
递归算法的时间复杂度求解有3种常见的方法：递推式，master定理，递归树。读者掌握其中1种如递推式求解即可。
递归算法的时间复杂度=每1次递归的时间复杂度*递归次数；递归算法的空间复杂度=每1次递归的空间复杂度*递归深度。
递归算法空间复杂度求解时要注意递归栈所需空间的考虑，往往与问题规模相关。
能将大问题分解为相似小问题时，可以想到递归算法。
学会建立递归模型，是使用递归算法求解问题的关键。
• 在选择非递归和递归算法时，可以参考表所示，比较它们优缺点再灵活应用。
