第二章：递归（Recursion）

一、什么是递归 (知识点)

1. 递归的定义

概念：在定义一个过程或函数时出现调用本过程或本函数的成分，称为递归。
分类：调用自身称为直接递归；过程p调用q，q又调用p称为间接递归（任何间接递归都可等价转换为直接递归）。
尾递归：如果递归调用语句是函数中的最后一条执行语句，则称为尾递归。

2. 使用递归解决问题的三个条件

问题可以转化为一个或多个子问题求解，且子问题的求解方法与原问题完全相同，只是在数量规模上不同。
递归调用的次数必须是有限的。
必须有结束递归的条件（递归出口）来终止递归。

3. 何时使用递归（三大场景）

定义的数学公式是递归的：如求阶乘 $n!$ 、Fibonacci数列、Ackerman函数。
数据结构是递归的：如单链表（结点中包含指向自身类型的指针）、二叉树。
问题的求解方法是递归的：如Hanoi塔问题。

4. 递归模型与执行过程

递归模型由两部分组成：
- 递归出口：确定递归到何时结束（如 $f(s_1)=m_1$ ）。
- 递归体：确定递归求解时的递推关系，即将“大问题”转化为“小问题”的组合（如 $f(s_{n+1})=g(f(s_i), c_j)$ ）。
底层执行过程：系统利用栈（系统栈）来为每一次调用开辟存储单元，保存返回地址和被中断函数的参量值。执行分为两步：分解过程（大问题化小问题直到出口）和求值过程（退栈计算并返回结果）。递归深度越深，开辟的栈空间越大。

二、递归算法设计方法与经典例题

设计步骤：①抽象出合理的小问题 $f(s_{n-1})$ ；②在此基础上确定 $f(s_n)$ 的解与 $f(s_{n-1})$ 的关系；③确定特定情况下的解作为递归出口。

例题 1：求数组的最大元素

题意：求包含 $n$ 个元素的整数数组 $a$ 的最大元素。
推导思路 (方法一)：将问题分为前 $n-1$ 个元素的最大值（小问题）和第 $n$ 个元素。递推关系为 $f(a, n) = \max\{f(a, n-1), a[n]\}$ ，出口为 $n=1$ 时返回 $a$ 。
推导思路 (方法二：分治思想)：采用二分法，求出左半段最大值 $max_1$ 和右半段最大值 $max_2$ ，取两者的较大者。出口为 $i=j$ （只有一个元素）时返回 $a[i]$ 。

例题 2：递归数据结构的算法设计（单链表）

题意1（释放单链表所有结点）：
- 推导：要释放首结点为 $L$ 的单链表，先递归释放以 $L\rightarrow next$ 为首的剩余链表，然后再释放 $L$ 结点本身（free(L)）。出口是 $L == NULL$ 时不做任何事。
题意2（逆序输出单链表的值）：
- 推导：要逆序输出，必须先通过递归调用 OutputFromTail(L->next) 输出后续结点，递归调用返回后，再执行 printf(L->data) 输出当前结点的值。出口为 $L!=NULL$ 的取反。

例题 3：由先序和中序序列创建二叉树

题意：给定二叉树的先序序列 $a$ 和中序序列 $b$ ，构造二叉链表。
推导：
- 先序序列的第一个元素 $a_0$ 必定是根结点。
- 在中序序列 $b$ 中找到 $a_0$ 的位置 $k$ （即 $b_k = a_0$ ）。
- 由此可知，中序序列中 $b_0 \dots b_{k-1}$ 为左子树（共 $k$ 个结点）， $b_{k+1} \dots b_{n-1}$ 为右子树（共 $n-k-1$ 个结点）。
- 递归创建左子树 CreateBTree(pre+1, in, k) 和右子树 CreateBTree(pre+k+1, in+k+1, n-k-1)，分别挂在根结点的左右指针上。

例题 4：集合的全排列问题

题意：求包含 $n$ 个元素的集合 $R=\{r_1, \dots, r_n\}$ 的所有排列。
推导：设 $perm(R)$ 为集合 $R$ 的全排列。当 $n=1$ 时 $perm(R)=(r)$ 。当 $n>1$ 时，全排列由分别以每个元素 $r_i$ 作为前缀，加上剩余元素集合 $R-\{r_i\}$ 的全排列构成，即组合 $(r_i)perm(R-\{r_i\})$ 。

例题 5：整数划分问题（⭐️极高频考点）

题意：将正整数 $n$ 无序拆分成最大加数不超过 $m$ 的几种方案，记为 $f(n, m)$ 。
推导（分五种情况讨论）：
1. 当 $n=1$ 或 $m=1$ 时：无论对方是多少，都只有 1 种划分（全由1组成或本身为1）， $f(n,m)=1$ 。
2. 当 $n<m$ 时：最大加数不可能超过 $n$ ，所以等价于 $f(n, n)$ 。
3. 当 $n=m$ 时：划分方案中包含 $m$ 的只有1种（即 $n$ 本身）；不包含 $m$ 的方案最大加数不超过 $n-1$ 。故 $f(n, n) = 1 + f(n, n-1)$ 。
4. 当 $n>m>1$ 时：划分为两部分。包含至少一个 $m$ 的情况，相当于把剩下的 $n-m$ 继续用不超过 $m$ 的数划分，即 $f(n-m, m)$ ；绝对不包含 $m$ 的情况，相当于用不超过 $m-1$ 的数划分，即 $f(n, m-1)$ 。两者相加得 $f(n,m) = f(n, m-1) + f(n-m, m)$ 。
例子计算： $f(6,4) = f(6,3) + f(2,4) = f(6,3) + f(2,2) = 7 + 2 = 9$ 。

例题 6：递归的简单选择排序与冒泡排序

简单选择排序推导：在序列 $a[i\dots n]$ 中找最小元素 $a[k]$ ，将其与 $a[i]$ 交换。然后对剩下的 $a[i+1\dots n]$ 递归调用 SelectSort(a, i+1, n)。出口是 $i=n$ 。
冒泡排序推导：将前 $n-i+1$ 个元素中的最大值通过相邻交换冒泡到最后。然后递归调用 BubbleSort(a, i+1, n) 对剩下的元素排序。

三、递归转化为非递归

直接转化法：直接用循环结构的算法替代递归（不需要栈）。如阶乘的循环实现。
间接转化法：用栈模拟系统底层运行过程，保存必须的信息。如树、图的遍历。

四、递归算法复杂度分析（四大方法）

递归算法的执行时间 $T(n)$ 可用递归方程描述，常用以下四种方法求解：

1. 替换法

原理：将递归公式不断展开、代换子问题的规模，通过多项式整理推导解。
例题：汉诺塔： $T(n) = 2T(n-1)+1$ 。展开为 $2(2T(n-2)+1)+1 = 2^2T(n-2)+2+1$ ……最终化简为 $T(n)=2^n-1 = O(2^n)$ 。
例题：二路归并排序： $T(n) = 2T(n/2) + c_2n$ 。展开为 $2^2T(n/2^2) + 2c_2n$ ，推导 $k$ 次后令 $n=2^k$ ，得 $T(n) = O(n\log_2n)$ 。

2. 特征方程法

原理：用于解 $K$ 阶常系数线性齐次/非齐次递归方程。
根不相同：若有 $k$ 个不同根 $q_i$ ，通解为 $T(n) = c_1q_1^n + c_2q_2^n + \dots + c_kq_k^n$ 。
有重根：若有 $r$ 个重根，通解会带有 $n$ 的多项式系数，如 $(c_i+c_{i+1}n+\dots)q_i^n$ 。
例题 1： $T(n) = 6T(n-1) - 11T(n-2) + 6T(n-3)$ $T (n) = 6 T (n - 1) - 11 T (n - 2) + 6 T (n - 3)$ ，初始 $T(0)=0, T(1)=2, T(2)=10$ $T (0) = 0, T (1) = 2, T (2) = 10$ 。
- 推导：特征方程 $x^3-6x^2+11x-6=0$ ，因式分解得根 $q_1=1, q_2=2, q_3=3$ 。
- 通解为 $T(n) = c_1 + c_2 2^n + c_3 3^n$ 。代入初始条件解得 $c_1=0, c_2=-2, c_3=2$ 。最终解为 $T(n) = 2(3^n - 2^n)$ 。
例题 2（Fibonacci数列）： $f(n)=f(n-1)+f(n-2)$ 。特征方程 $x^2-x-1=0$ ，解得根为 $\frac{1\pm\sqrt{5}}{2}$ ，代入初始值得解 $O((\frac{1+\sqrt{5}}{2})^n)$ 。

3. 递归树法

原理：展开递归方程构造递归树，把每一层的时间进行求和得出估计。
例题 1： $T(n) = 2T(n/2) + n^2$ 。第一层代价 $n^2$ ，第二层 $2 \times (n/2)^2 = n^2/2$ ，第三层 $n^2/4$ 。求和得 $n^2(1 + 1/2 + 1/4 + \dots) = O(n^2)$ 。
例题 2（不平衡树）： $T(n) = T(n/3) + T(2n/3) + n$ 。每层的和均为 $n$ 。最长路径高度为 $\log_{3/2}n$ 。总和等于树高乘层和，即 $O(n \log_{3/2} n) = O(n\log_2n)$ 。

4. 主方法 (Master Method)

原理：针对形式为 $T(n) = aT(n/b) + f(n)$ 的方程（ $a\ge1, b>1$ ）。
三大情况（通过比较 $f(n)$ $f (n)$ 与 $n^{\log_b a}$ $n^{l o g_{b} a}$ ）：
1. 若 $n^{\log_b a}$ 大（呈多项式大于），则 $T(n) = O(n^{\log_b a})$ 。
2. 若 $n^{\log_b a}$ 与 $f(n)$ 一样大（同阶），则 $T(n) = O(n^{\log_b a} \log n)$ 。
3. 若 $f(n)$ 更大且满足正则条件，则 $T(n) = O(f(n))$ 。
例题 1： $T(n) = 4T(n/2) + n$ 。 $a=4, b=2, f(n)=n$ 。计算 $n^{\log_2 4} = n^2$ 。因为 $n^2$ 比 $f(n)=n$ 大，属情况1，故 $T(n) = O(n^2)$ 。
例题 2： $T(n) = 2T(n/2) + n^2$ 。 $a=2, b=2, f(n)=n^2$ 。计算 $n^{\log_2 2} = n$ 。因为 $n$ 比 $f(n)=n^2$ 小，属情况3，故 $T(n) = O(n^2)$ 。