第 5 章 递归
5.1 什么是递归
1. 定义
递归（Recursion）：在定义一个过程或函数时出现调用本过程或本函数的成分，称为递归。
若调用自身，称为直接递归（Direct Recursion）。若过程或函数 p 调用过程或函数 q ，而 q 又调用 p ，称为间接递归（Indirect Recursion）。
在算法设计中，任何间接递归都可以转换为直接递归来实现，所以本章仅讨论直接递归。
如果一个递归过程或递归函数中的递归调用语句是最后一条执行语句，则称这种递归为尾递归（Tail Recursion）。例如阶乘：
n
!
=
1
×
2
×
3
×
⋯
×
n
n!=1\times2\times3\times\cdots\times n
n!=1×2×3×⋯×n ，并规定
0
!
=
1
0!=1
0!=1 。用递归的方式表示：
f
(
n
)
=
{
1
i
f
n
=
0
n
⋅
f
(
n
−
1
)
i
f
n
>
0
\begin{split} f(n)=\begin{cases}1&\quad if~n=0\\n\cdot f(n-1)&\quad if ~n\gt0\end{cases} \end{split}
f(n)={1n⋅f(n−1)if n=0if n>0 【算法描述】
long factorial(int n){
if(n == 0){
return 1;
} else {
return n * factorial(n - 1);
}
}
这个递归函数，是直接递归，也是尾递归。
2. 使用条件
递归算法通常把一个大的复杂问题层层转化为一个或多个与原问题相似的规模较小的问题来求解，递归策略只需少量的代码就可以描述出解题过程中所需要的多次重复计算，大大减少了算法的代码量。
一般来说，能够用递归解决的问题应该满足以下 3 个条件：
需要解决的问题可以转化为一个或多个子问题来求解，而这些子问题的求解方法与原问题完全相同，只是在数量规模上不同；递归调用的次数必须是有限的；必须有结束递归的条件来终止递归。
3. 使用递归的时机
以下三种情况下有可能用到递归方法。
（1）定义是递归的
比如阶乘
n
!
n!
n! ，以及学过的斐波那契数列等，这些均可用递归定义。
（2）数据结构是递归的
以单链表为例：
typedef struct LNode{
ElemType data; //结点的数据域
struct LNode * next; //结点的指针域
}LNode, *LinkList; //LinkList 为指向结构体 LNode 的指针类型
单链表的每个结点 LNode 由数据域 data 和指针域 next 组成，而指针域 next 是一种指向 LNode 类型的指针，即 LNode 的定义中又用到了其自身，所以单链表是一种递归的数据结构。
像单链表这样的具有递归特性的数据结构，它们的操作也可以递归地描述。
例如，遍历单链表结点并输出。一种方法是用迭代的方式，也就是用循环语句实现。本节要介绍另一种方法，即根据前述链表数据结构的特点，使用递归方法实现。其基本思想是：首先让指针 p 指向单链表的首元结点，在递归过程中，p 不断向后移动，指向后继结点，直到 p 为 NULL 时递归结束。
【算法步骤】
如果 p 为 NULL ，递归结束返回。否则，输出 p->data ，p 指向后继结点继续递归。
【算法描述】
void TraverseList(LinkList p){
if (p == NULL) return; //递归终止
else{
cout<< p->data << endl; //输出当前结点的数据域
TraverseList(p->next); //p 指向后继结点继续递归
}
}
上述写法是严格按照【算法步骤】的描述实现的，其实，第 2 行可以省略，因为 else 分支下的语句，只有在 p 为真的条件下执行。故可简化为：
void TraverseList(LinkList p){
if (p) {
cout<< p->data << endl; //输出当前结点的数据域
TraverseList(p->next); //p 指向后继结点继续递归
}
}
除了这里所介绍的单链表是具有递归特性的数据结构，后续会讲到的二叉树、广义表也都是具有递归特性的数据结构。
（3）问题的解法是递归的
有时问题本身不像斐波那契数列那样有明显的递归，但是，如果用递归方法求解该类问题，却是一种简单的思维方法，通常比使用迭代方法更简单。比如，典型的汉诺塔问题（Tower of Hanoi）。
汉诺塔是根据一个传说形成的数学问题，最早是由法国数学家爱德华·卢卡斯提出。
有三根杆子 A，B，C 。A 杆上有 N 个
(
N
>
1
)
(N>1)
(N>1) 穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：
每次只能移动一个圆盘；大盘不能叠在小盘上面。
问：如何移动？最少要移动多少次？
下面链接是一个汉诺塔问题的交互操作程序，读者可以通过操作，尝试解决此问题。https://www.mathsisfun.com/games/towerofhanoi.html
图 5.1.1 汉诺塔问题的求解过程
如图 5.1.1 所示。假设 A 柱上最初的盘子总数为
n
n
n 。
当
n
=
1
n=1
n=1 时，只要将编号为 1 的圆盘从 A 直接移至 C 上即可。否则，执行如下三步：
用 C 柱做过渡，将 A 柱上的
(
n
−
1
)
(n-1)
(n−1) 个盘子移到 B 柱上；将 A 柱上最后一个盘子直接移到 C 柱上；用 A 柱做过渡，将 B 柱上的
(
n
−
1
)
(n-1)
(n−1) 个盘子移到 C 柱上。
由上述求解过程可知，汉诺塔问题符合分治算法的递归求解要求。
【算法步骤】
如果
n
=
1
n=1
n=1 ，则直接将编号为 1 的圆盘从 A 移到 C，递归结束。否则：
递归，将 A 上编号为 1 至
n
−
1
n-1
n−1 的圆盘移到 B，C 做辅助塔；直接将编号为 n 的圆盘从 A 移到 C；递归，将 B 上编号为 1 至
n
−
1
n-1
n−1 的圆盘移到 C，A 做辅助塔。
【算法描述】
//定义搬动操作函数 move(A, n, C) ，将编号为 n 的圆盘
// 从 A 移到 C。
//用全局变量 m 对搬动次数计数
int m = 0;
void move(char A, int n, char C){
cout << ++m <<"," << n << "," << A << "," << C << endl;
}
void Hanoi(int n, char A, char B, char C){
//将 A 上的 n 个圆盘移到 C 上，B 做辅助塔
if (n == 1) move(A, 1, C); //将编号为 1 的圆盘从 A 移到 C
else {
Hanoi(n-1, A, C, B); //将 A 上不编号为 1 至 n-1 的圆盘移到 B ，C 做辅助塔
move(A, n, C); //编号为 n 的圆盘从 A 移到 C
Hanoi(n-1, B, A, C); //将 B 上编号为 1 至 n-1 的圆盘移到 C，A 做辅助塔
}
}
【算法分析】
假设圆盘数量为
n
n
n 时，移动圆盘的时间复杂度为
T
(
n
)
T(n)
T(n) ；圆盘数量为
(
n
−
1
)
(n-1)
(n−1) 时时间复杂度
T
(
n
−
1
)
T(n-1)
T(n−1) 。根据算法，要将
n
−
1
n-1
n−1 个圆盘从 A 移到 B（借助 C），然后将这些圆盘从 B 移到 C（借助 A）。再加上将编号为 n 的圆盘从 A 移到 C 所花费的常数时间（用
c
c
c 表示）则得到递推公式：
T
(
n
)
=
2
T
(
n
−
1
)
+
c
T(n)=2T(n-1)+c
T(n)=2T(n−1)+c 根据递推公式，有：
T
(
n
)
=
2
T
(
n
−
1
)
+
c
=
2
[
2
T
(
n
−
2
)
+
c
]
+
c
=
2
2
T
(
n
−
2
)
+
[
2
+
1
]
c
=
2
2
[
2
T
(
n
−
3
)
+
c
]
+
[
2
+
1
]
c
=
2
3
T
(
n
−
3
)
+
[
2
2
+
2
+
1
]
c
⋮
=
2
n
−
1
T
(
1
)
+
[
2
n
−
2
+
⋯
+
2
0
]
c
\begin{split} T(n)&=2T(n-1)+c=2[2T(n-2)+c]+c \\&=2^2T(n-2)+[2+1]c=2^2[2T(n-3)+c]+[2+1]c \\&=2^3T(n-3)+[2^2+2+1]c \\&~\vdots \\&=2^{n-1}T(1)+[2^{n-2}+\cdots+2^0]c \end{split}
T(n)=2T(n−1)+c=2[2T(n−2)+c]+c=22T(n−2)+[2+1]c=22[2T(n−3)+c]+[2+1]c=23T(n−3)+[22+2+1]c ⋮=2n−1T(1)+[2n−2+⋯+20]c 显然
T
(
1
)
=
c
T(1)=c
T(1)=c
上述汉诺塔问题算法的时间复杂度是
O
(
2
n
)
O(2^n)
O(2n) ，即指数阶的时间复杂度。
在第 2 章已经研究过这种指数阶时间复杂度，在一般情况下， 无法用于解决实际问题，不是一个有效的算法。
对于汉诺塔问题的时间复杂度分析，也可以通过计算移动盘子的次数得到，借用前面给出的交互演示程序和算法，可知：
圆盘数量
n
n
n移动圆盘次数1
1
=
2
1
−
1
1=2^1-1
1=21−12
3
=
2
2
−
1
3=2^2-1
3=22−13
7
=
2
3
−
1
7=2^3-1
7=23−1
⋮
\vdots
⋮
⋮
\vdots
⋮n
2
n
−
1
2^{n}-1
2n−1
因此时间复杂度为
O
(
2
n
)
O(2^n)
O(2n) 。