算法：递归法

定义

若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的；若一个过程直接或间接地调用自己，则称这个过程是递归的过程。

递归的三种情况：定义是递归的、数据结构是递归的、问题的解法是递归的。

递归的特点：递归至少存在一个出口、函数内部自己调用自己。

问题举例

阶乘

阶乘的定义：

$$ n! = \left\{ \begin{array}{c} 1, & n = 0 \\ n \cdot (n-1)!, & n \geqslant 1 \end{array} \right.$$

可知阶乘的定义是递归的。

1
2
3
4
5
6
7
8


long long Factorial(long long n) {
    if (n == 0) {
        return 1;
    }
    else {
        return n * Factorial(n-1);
    }
}

查找链表的元素

定义链表：

1
2
3
4


struct Node {
    ElemType data;
    Node *next;
};

可知链表的数据结构是递归的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


void Search(Node *f, ElemType e) {
    if (f != NULL) {
        if (f->data == x) {
            printf("%d\n", f->data);
        }
        else {
            Search(f->next, e);
        }
    }
    return;
}

汉诺塔问题

问题概述：假设有3个分别命名为 $x$，$y$，$z$ 的塔座，在塔座 $x$ 上插有 $n$ 个直径大小各不相同、依次编号为 $1,2,3,…,n$ 的圆盘。现要求将 $x$ 塔座的 $n$ 个圆盘移动到 $z$ 塔座上且按同样的顺序堆叠。圆盘移动时遵循以下规则：

每次只能移动一个圆盘。
圆盘可以放在 $x$，$y$，$z$ 的任意塔座上。
任何时刻都不能将一个较大的圆盘放在较小的圆盘之上。

汉诺塔

考虑规模为 $n$ 的汉诺塔，移动可分为以下三步：

先将 $n-1$ 个圆盘移动到 $y$ 塔座上；
再将第 $n$ 个大圆盘移动到 $z$ 塔座上；
最后将 $n-1$ 个圆盘移动到 $z$ 塔座上。

其中，第一步和第三步即可视为规模为 $n-1$ 的汉诺塔问题。因此，汉诺塔问题的解法是递归的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


void hanoi(int n, char x, char y, char z) {
    if (n == 1) {
        move(x, 1, z);          // 将编号为1的圆盘从x移到z
    }
    else {
        hanoi(n-1, x, z, y);    // 将x上编号为1到n-1的圆盘移到y，z作为辅助塔
        move(x, n, z);          // 将编号为n的圆盘从x移到z
        hanoi(n-1, y, x, z);    // 将y上编号为1到n-1的圆盘移到z，x作为辅助塔
    }
}

分析递归方程：

$$T(n) = 2T(n-1) + \Theta(1)$$

可知求解汉诺塔问题（输出移动方式）的时间复杂度为 $\Theta(2^n)$。

如果只需要输出总的移动步数，则使用通项公式 $a_n = 2^n - 1$ 即可。

递归算法的改进

记忆化搜索

记忆化搜索（Memoization）是递归算法中一种“以空间换时间”的优化技术，核心思想是把重复计算的子问题结果存起来，避免递归树中的指数级爆炸。

它本质上是动态规划的一种自顶向下实现方式，特别适合解决具有重叠子问题和最优子结构性质的问题。

步骤：

建立备忘录：用数组/哈希表存储已计算的状态，初始化为“未计算”标志（如 -1 或 null）。
改写递归函数：进入函数后，先查备忘录，若已计算则直接返回。否则计算，存表，再返回。

例如，对于斐波那契数列

$$F(n) = \left\{\begin{align*} & 1, & n=1,2 \\ & F(n-1) + F(n-2), & n \geqslant 3 \end{align*}\right.$$

普通递归算法如下：

1
2
3
4


int fib(n) {
    if (n <= 2) return 1;
    return fib(n-1) + fib(n-2);  
}

使用记忆化搜索后的递归：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


int fib_memo(n) {
    // 0 表示未计算
    memset(memo, 0, n);       
    return dfs(n);
}

int dfs(k) {
    if (k <= 2) return 1;
    // 已计算，直接返回
    if (memo[k] != -1) return memo[k];
    memo[k] = dfs(k-1) + dfs(k-2);
    return memo[k];
}

与动态规划（自底向上）的区别：

维度	记忆化搜索（自顶向下）	传统 DP（自底向上）
计算顺序	从大问题递归到小问题	从小问题开始迭代到大问题
代码风格	递归 + 备忘录	循环 + 数组递推
计算量	只计算需要的状态	通常计算所有状态
空间优化	较难（依赖递归栈）	容易用滚动数组
实现难度	直观，符合数学定义	需要明确状态转移顺序

递归转换为递推

递归：从大问题出发，假设子问题已解决，不断分解。比如计算 $f(10)$，先算 $f(9)$，再算 $f(8)$ ……直到 $f(0)$。
递推：从最小子问题出发，主动计算并存储结果，逐步构建出大问题。比如先算 $f(0)$，再算 $f(1)$，最后推到 $f(10)$。

转换的本质就是手动模拟递归栈，把“系统帮我们压栈”变成“我们用数组/变量显式存储状态”。