当前课程知识点：数据结构 > 第3章 栈和队列 > 3.4 栈与递归 > 讲解（上）
在学习了栈数据结构之后
我们接下来看看栈和递归。先来看递归，递归是一类常用的算法思想
递归的本质就是：算法当中的某一步或者某几步，是由算法本身构成的
而后者涉及的问题规模，通常是更小的
对于编程来说
递归是指函数自己调用了自己
递归可以用于解决一些用常规方式难以解决的问题
我们后面会看到几个例子
现在，我们来看看，哪些问题
可以采用递归，或者说递归问题可以分为哪几类
我们先来看第一类：问题的定义是递归的
这里，我们以数学上的求阶乘为例
我们知道，n!=n*(n-1)!
而0!是已知的
直接等于1
求(n-1)!
实际上，又会递归到求(n-2)!
一直往下，直到要求的阶乘n
是等于0的
这时候，就不用再递归了
而直接得到结果1
然后，再逐层地返回
现在，我们来看，用递归方式来求阶乘的代码
函数名叫f，参数是n
我们要求n!，返回值
是long型的
因为，n!可能会很大
如果n等于0
是不需要递归的
直接返回1
除此之外
n>0的情况，都进行递归
那么，就套用上面这个式子
n*f(n-1)，大家看到，函数体当中，某一步自己调用了自己
但是，传入的参数
不太一样
一般来说，这个参数是越来越小的
也就是所谓的问题
规模越来越小
这样一个程序
我们把它写的简化一点
实际上，用一行语句就可以了
我们用C语言的选择运算符
条件运算符
如果n等于0，我们直接返回1
除此之外
我们返回n*f(n-1)
这是最简单形式的递归
现在，我们来看，第二类递归：问题结构是递归的
我们给出的问题是：得到非空单链表的最后一个元素
大家看到，这样一个单链表，一共包含4个元素
最后一个元素
是a4
如果我们用常规的方式来求解
肯定是写一个循环，从头指针
L开始
不断地让一个指针，指向后面的结点
当指针指向的
结点的next为空的时候
这时候，指针p指向的结点的数据域，就是我们要求解的结果
现在，我们可以换一种思路
原问题是求
L指向这个头结点的单链表
它的最后一个元素
现在把问题转换成：L指向
a1这个结点，也就是以a1为头结点的单链表
你会发现，这个单链表，它的最后一个元素跟原问题的最后一个元素是相同的
但是，表长却少了1
我们可以采用类似的思想
让L继续往后，一直往后
当L是一个空链表的时候
注意，L指向的是头结点
当L指向的结点
它的next为空的时候
这时候，L指向的结点
它的数据域，就是我们要求解的原问题中的最后一个结点
现在，我们给出代码的实现
得到单链表的最后一个元素
单链表的头指针是L
因为要求结点的数据域
所以，我们给出的返回值类型是ElemType
我们直接用一行语句
如果L->next是空，注意，!L->next等价于
L->next为空
也就是这种情形
一个空的单链表
L->next为空
我们直接返回L->data
返回它的数据域
除此之外
如果
L->next不为空
那么，我们就递归，自己调用自己
但是，这时候传入的实参是有变化的
不再是L
而是L->next
也就是
指向这里
一直递归下去
最终，L会指向最后一个结点
这是问题结构是递归的
我们再来看第三类递归
求解思想是递归的
这里，我们引入的例子
是著名的汉诺塔游戏，汉诺塔游戏
它的规则很简单
三个柱子
A
B
C
A柱子上，有大小不等的若干个盘子，编号从上到下
是#1到#n
原问题是这样要求的
将A上的n个盘子，移动到C上
也就是，最终要到达这样一种状态
在移动的过程当中
有几个限定条件
第一，每次只能移动一个盘子
第二个限定条件
在移动的过程当中，只能将小盘子
压在大盘子上，不能将大盘子压在小盘子上
这样一个问题，我们如何来做呢
我们采用递归的思想
可以分为三步来做
第一步
我们先将A上的前n-1个盘子
注意，是不包含
#n盘的
是#1到#n-1盘
前n-1个盘子
我们先从A
移动到B上
也就是，到这样一种情况
然后，A上剩的#n盘
编号为n的那个盘子
我们直接移到C上
这是第二步
第三步
我们再将B上的n-1个盘子，从B挪到C上
这样，问题就最终求解了
但是
这三步当中，有两步是无法直接求解的
只有第二步，是可以直接移动的
比如，第二步将A上的#n盘，直接从A移到C上，这是可以直接移的
因为只有一个盘子
而C上没有其他的盘子
第一步和第三步都是递归
但是，问题的规模变小了
第一步，是移A上的#1到#n-1盘
它比原来的#1到#n盘
少了一个
我们将n-1个盘子，从A挪到B上
这是第一步做的事情
第三步
是将B上的
#1到#n-1盘子，从B挪到C上
这一步，也是无法直接求解的
所以一、三两步是递归，我们在这里，可以简单地写一下原问题
它是：移动
#1到#n盘，从A到C
这是原问题
我们把这个原问题
拆成三步，第一步
是：移动
#1到#n-1盘
从A挪到B上
B实际上是用于暂存盘子的，临时存放
一些盘子；第二步，A上只有编号为n的一个盘子了
这时候，我们可以直接移动，移动#n盘子，从A
到C上，这一步是可以直接求解的
第三步
将B上的
#1到#n-1盘子，从B
再挪到C上
大家观察一下，原问题
拆分成的三个步骤
第二步，是可以直接求解的
而第一步
跟第三步，是无法直接求解的
但是，你会发现，这两步它们的问题性质，跟原问题是一模一样的
都是将若干个盘子，从某一个柱子移到另外一个柱子
但是
一、三两步
它们的问题规模变小了
原来是移n个盘子
一、三却是移n-1个盘子
一、三它们可以继续拆成三步
一直往后递归
在拆的过程当中，最终
会到达只移1个盘子的情况
这时候，递归就返回了
最终，将原问题求解
现在，我们给出完整的代码
参数是这样的
第1个参数，是代表一共多少个盘子
从哪个柱子，经过哪个临时的柱子，移到哪个柱子上
我们这里，从A柱，经过
temp这样一个临时的柱子
最终，移到C上，一共n个盘子
如果n等于1
也就是，仅仅只有一个盘子
那我们就直接移动，move
我们在上面给出来，它的第1个参数，实际上是用来做计数的
表示当前是第几次移动；后面3个参数：移动
哪一个盘子，从哪个柱子，移到哪个柱子上
我们把它打印出来
以方便大家理解
我们这里
直接将A上的#1盘
因为，这时候n等于1
实际上，也可以写成n，将A上的#n盘，从A移到C上
当n>1的时候
我们就进入递归
我们现在将A上的#1到
#n-1盘子
以C为临时的柱子
把它们移到temp上
注意，这2个参数的顺序有变化
我们现在是以C为临时的柱子
将它们移到temp上
暂存起来，也就是相当于图当中的B
然后，第二步是可以直接求解的
因为A上的前
n-1盘子移出来之后，只剩下#n盘了
这时候，我们直接将#n盘
从A移到C上
第三步
我们再将temp上的
#1到#n-1号盘子，从temp，经过A为临时的柱子
最终移到C上，注意，我们在声明count的时候
前面加了一个关键字static
因为，如果不加这个关键字
每一次递归进来，都要重新初始化
count为0，那我们打印的第几次移动，就不对了
我们只让它初始化一次
加一个static
第一次执行到这一行的时候，初始化它为0，以后
再执行到这一行，就不执行了
而是用上一次count的值
否则，每次这里打印的count，它的值就不对了
而且，我们这里采用了引用参数的语法
因为，我们在函数内部会对count进行自增
现在，来看递归算法
任何递归算法实际上都由两部分组成
第一部分：终结条件，终结条件是指无需递归，就能直接得到结果的那些部分
比如，我们刚才将一个柱子上的一个盘子，移到另外一个柱子上
这时候，是不需要递归的
直接移就可以了
第二部分，就是所谓的递归部分
这时候，将原问题拆分成性质相同
但规模更小的若干个子问题
所谓性质相同
就是子问题要做的事情，跟原问题是一样的
只不过，相关的参数不一样，参数的大小、要处理的数据规模不一样而已
所以
所有的递归算法，从整体上都可以认为是一个
if-else语句
我们这里，写出递归算法的大致的架构
算法名字是solution——解决方案
我们这里直接用scale代表原问题的问题规模，当问题规模满足终结条件的时候
这个就是递归的第一部分
当问题规模满足终结条件的时候
我们是直接得到结果
那么
如果不满足终结条件
我们就递归
但是，传入的参数有变化，是更小的问题规模，而不是原来的问题规模
就像前面，原来是n个盘子
但现在是n-1个盘子
还类似于刚才求阶乘，求n的阶乘转换成
求n-1的阶层，是一样的
问题规模越来越小
当小到一定程度的时候，会触发终结条件
从而直接得到结果
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
