第二章：递归（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(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)$ 与 $n^{\log_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)$。