算法基础篇：（十四）基础算法之递归初阶：从汉诺塔到 FBI 树，解锁递归的奥秘

前言

在算法的世界里，递归是一种既神奇又充满魅力的思想。它就像一面镜子，让函数自己调用自己，将复杂的问题拆解成一个个相似的子问题，直到子问题简单到可以直接求解。对于刚接触算法的小伙伴来说，递归可能一开始会让人觉得困惑，但一旦掌握了它的核心思想，就能发现它在解决各类问题时的强大威力。今天，我们就一起走进递归初阶的世界，从经典的汉诺塔问题入手，再到趣味的占卜 DIY 和 FBI 树问题，一步步揭开递归的神秘面纱。下面就让我们正式开始吧！

一、递归是什么？

在正式开始讲解例题之前，我们首先要搞清楚：递归到底是什么？

递归，简单来说就是函数自己调用自己。它的核心思想是分治，把一个规模较大的问题分解为若干个规模较小的、与原问题结构相同的子问题，然后通过解决这些子问题，最终合并得到原问题的解。

递归有两个必不可少的条件：

1. 递归终止条件：当问题小到一定程度时，直接给出答案，不再继续递归，否则函数会无限调用自己，导致栈溢出。
2. 递归递推关系：将大问题分解为子问题的规律，子问题的解法必须和原问题的解法一致。

举个最简单的例子，计算阶乘 n!（n! = n × (n-1) × (n-2) × ... × 1），用递归实现的话，递推关系是 n! = n × (n-1)!，终止条件是 0! = 1、1! = 1。对应的 C++ 代码如下：

#include <iostream>
using namespace std;

// 递归计算n的阶乘
int factorial(int n) {
    // 递归终止条件
    if (n == 0 || n == 1) {
        return 1;
    }
    // 递推关系：n! = n * (n-1)!
    return n * factorial(n - 1);
}

int main() {
    int n;
    cout << "请输入一个正整数：";
    cin >> n;
    cout << n << "的阶乘是：" << factorial(n) << endl;
    return 0;
}

这段代码中，factorial函数不断调用自身，每次传入的参数n减 1，直到n为 1 或 0 时停止递归，开始回溯计算结果。这就是递归最基础的应用，而接下来我们要讲的问题，会让你对递归有更深入的理解。

二、经典递归：汉诺塔问题

汉诺塔问题是递归算法的 “Hello World”，几乎所有讲解递归的教材都会提到它。这个问题不仅能帮助我们理解递归的核心思想，还能锻炼我们拆解问题的能力。

题目链接如下：http://ybt.ssoier.cn:8088/problem_show.php?pid=1205

2.1 问题描述

约 19 世纪末，欧洲出现了一种智力玩具：一块铜板上有三根杆，最左边的杆上自上而下次串着由 64 个圆盘构成的塔，圆盘从小到大排列。目的是将最左边杆上的圆盘全部移到中间的杆上，条件是：

1. 一次只能移动一个圆盘；
2. 不允许大盘放在小盘的上面。

我们的任务是，给定圆盘的数目n和三根杆的编号，输出每一步的移动记录。

2.2 问题分析

我们先从最简单的情况入手，逐步推导递归的规律：

• 当 n=1 时：只有一个圆盘，直接将它从起始杆移到目标杆即可，这是递归的终止条件。
• 当 n=2 时：需要借助中间杆作为中转。先把小圆盘移到中间杆，再把大圆盘移到目标杆，最后把小圆盘从中间杆移到目标杆，共 3 步。
• 当 n=3 时：可以把上面 2 个圆盘看作一个整体，先借助目标杆将这 2 个圆盘移到中间杆，再把最大的圆盘移到目标杆，最后借助起始杆将中间杆上的 2 个圆盘移到目标杆。而移动 2 个圆盘的过程，正是 n=2 时的解法 —— 这就是递归的递推关系！

由此可以总结出汉诺塔问题的递归策略：对于n个圆盘，要从起始杆begin移到目标杆end，借助中转杆tmp：

1. 先将begin上的n-1个圆盘借助end移到tmp；
2. 再将begin上剩下的 1 个最大圆盘移到end；
3. 最后将tmp上的n-1个圆盘借助begin移到end。

2.3 代码实现

根据上述分析，我们可以写出汉诺塔问题的 C++ 递归实现：

#include <iostream>
using namespace std;

int n;
char a, b, c;

// 将x个盘子从begin杆移动到end杆，tmp杆作为中转
void move(int x, char begin, char tmp, char end) {
    // 递归终止条件：没有盘子需要移动
    if (x == 0) {
        return;
    }
    // 第一步：将n-1个盘子从begin移到tmp，借助end
    move(x - 1, begin, end, tmp);
    // 第二步：将最大的盘子从begin移到end
    printf("%c->%d->%c\n", begin, x, end);
    // 第三步：将n-1个盘子从tmp移到end，借助begin
    move(x - 1, tmp, begin, end);
}

int main() {
    // 输入：盘子数目 + 三根杆的编号
    cin >> n >> a >> b >> c;
    // 把a杆上的n个盘子，借助c杆转移到b杆
    move(n, a, c, b);
    return 0;
}

2.4 代码测试

输入示例：

2 a b c

输出结果：

a->1->c
a->2->b
c->1->b

这是与我们手动推导的步骤完全一致的。当n增大时，递归会自动处理n-1个圆盘的移动过程，无需我们手动干预 —— 这就是递归的优雅之处。

三、趣味递归：占卜 DIY

如果说汉诺塔是递归的经典入门题，那么占卜 DIY 就是一道充满趣味性的递归模拟题。这道题不仅能巩固我们对递归的理解，还能锻炼我们处理复杂流程的能力。

题目链接如下：https://www.luogu.com.cn/problem/P10457

3.1 问题描述

占卜的规则如下：

1. 一副去掉大小王的扑克共 52 张，打乱后均分为 13 堆，编号 1~13，每堆 4 张，其中第 13 堆为 “生命牌”，代表 4 条命；
2. 牌中的 K（编号 13）被称作死神，抽到 K 则失去一条命，扔掉 K 后重新从生命牌的最上面抽牌；
3. 抽牌流程：抽取生命牌最上面的牌，翻开后放到牌面数字对应编号的堆的最上边，再从该堆的最底下抽取一张牌，重复此过程，直到抽到 K；
4. 当 4 条命都耗尽后，统计每堆牌中正面朝上的牌的数目，同一数字出现 4 张正面朝上则为 “开了一对”（K 不算），最终统计开对的数量。

我们的任务是根据输入的每堆牌的具体内容，模拟占卜过程，输出开对的数量。

3.2 问题分析

这道题的核心是模拟抽牌的递归过程：每次抽到一张牌x（非 K），就需要从第x堆的最后一张抽牌，然后重复抽牌流程；如果抽到 K，则终止当前递归，消耗一条命后重新开始。

首先，我们需要将牌的字符表示（如 A、J、Q、K）转化为数字：A→1，J→11，Q→12，K→13，0（代表 10）→10。然后用数组存储每堆牌的内容，用一个辅助数组记录每堆牌剩余的牌数，方便抽取最后一张牌。

递归的核心逻辑是：定义dfs(x)函数，表示抽到了数字为x的牌，执行以下操作：

1. 如果x == 13（抽到 K），直接返回，消耗一条命；
2. 否则，从第x堆的最后一张抽取牌t；
3. 将第x堆的剩余牌数减 1；
4. 递归调用dfs(t)，继续处理抽到的新牌t。

3.3 代码实现

下面是占卜 DIY 问题的 C++ 递归实现：

#include <iostream>
using namespace std;

const int N = 15, M = 6;
// n=13堆牌，m=4张每堆
int n = 13, m = 4;
// a[i][j]存储第i堆的第j张牌
int a[N][M];
// cnt[i]记录第i堆剩余的牌数
int cnt[N];
// mp[i]标记数字i是否开对
bool mp[N];

// 递归处理抽到的牌x
void dfs(int x) {
    // 抽到K，终止递归
    if (x == 13) {
        return;
    }
    // 拿到第x堆的最后一张牌
    int t = a[x][cnt[x]];
    // 第x堆剩余牌数减1
    cnt[x]--;
    // 继续处理抽到的新牌t
    dfs(t);
}

int main() {
    // 读入每堆牌的内容，并转化为数字
    for (int i = 1; i <= n; i++) {
        cnt[i] = 4;
        for (int j = 1; j <= m; j++) {
            char ch;
            cin >> ch;
            if (ch >= '2' && ch <= '9') {
                a[i][j] = ch - '0';
            } else if (ch == 'A') {
                a[i][j] = 1;
            } else if (ch == '0') {
                a[i][j] = 10;
            } else if (ch == 'J') {
                a[i][j] = 11;
            } else if (ch == 'Q') {
                a[i][j] = 12;
            } else if (ch == 'K') {
                a[i][j] = 13;
            }
        }
    }

    // 处理生命牌（第13堆）的4张牌，对应4条命
    for (int j = 1; j <= m; j++) {
        dfs(a[n][j]);
    }

    // 统计开对的数量
    int ret = 0;
    for (int i = 1; i <= n; i++) {
        // 某数字的牌全部正面朝上（剩余牌数为0），且不是K
        if (cnt[i] == 0 && i != 13) {
            ret++;
        }
    }
    cout << ret << endl;

    return 0;
}

3.4 代码测试

输入示例：

8 5 A A
K 5 3 2
9 6 0 6
3 4 3 4
3 4 4 5
5 6 7 6
8 7 7 7
9 9 8 8
9 0 0 0
K J J J
Q A Q K
J Q 2 2
A K Q 2

输出结果：

9

这个结果表示最终开了 9 对，对应题目中的 “小吉” 等级。通过递归模拟抽牌的过程，我们完美复现了占卜的流程，这也体现了递归在处理循环性流程问题时的灵活性。

四、进阶递归：FBI 树

FBI 树问题是递归在二叉树构造中的典型应用，它结合了字符串处理、二叉树递归构造和后序遍历，是对递归思想的综合考察。

题目链接如下：

4.1 问题描述

我们可以把由 “0” 和 “1” 组成的字符串分为三类：

• 全 “0” 串称为 B 串；
• 全 “1” 串称为 I 串；
• 既含 “0” 又含 “1” 的串称为 F 串。

由一个长度为2^N的 “01” 串 S 可以构造出一棵 FBI 树 T，递归构造方法如下：

1. T 的根结点类型与串 S 的类型相同；
2. 若串 S 的长度大于 1，将 S 从中间分开为等长的左右子串 S1 和 S2，由 S1 构造根的左子树 T1，由 S2 构造根的右子树 T2。

我们的任务是，给定一个长度为2^N的 “01” 串，构造出对应的 FBI 树，并输出它的后序遍历序列。

4.2 问题分析

要解决这个问题，我们需要拆解为三个核心步骤：

1. 判断字符串类型：对于一段区间的字符串，判断它是 B、I 还是 F 串。可以用前缀和数组快速统计区间内 “1” 的个数：
   • 若 “1” 的个数为 0，是 B 串；
   • 若 “1” 的个数等于区间长度，是 I 串；
   • 否则是 F 串。
2. 递归构造 FBI 树：将字符串不断从中间二分，递归构造左子树和右子树，直到字符串长度为 1（递归终止条件）。
3. 后序遍历 FBI 树：后序遍历的顺序是 “左子树→右子树→根结点”，在递归构造树的过程中，直接按此顺序输出结点类型即可，无需显式构建树结构。

4.3 代码实现

结合前缀和与递归，我们可以写出 FBI 树问题的 C++ 实现：

#include <iostream>
#include <string>
using namespace std;

int n;
// 前缀和数组，sum[i]表示前i个字符中'1'的个数
int sum[1 << 11];
string s;

// 递归处理区间[l, r]，构造FBI树并输出后序遍历
void dfs(int l, int r) {
    // 递归终止条件：区间长度为1
    if (l > r) {
        return;
    }

    // 判断当前区间的字符串类型
    char node_type;
    int one_count = sum[r] - sum[l - 1];
    int len = r - l + 1;
    if (one_count == 0) {
        node_type = 'B';
    } else if (one_count == len) {
        node_type = 'I';
    } else {
        node_type = 'F';
    }

    // 区间长度为1，直接输出类型
    if (l == r) {
        cout << node_type;
        return;
    }

    // 递归构造左子树和右子树
    int mid = (l + r) / 2;
    dfs(l, mid);       // 处理左子树
    dfs(mid + 1, r);   // 处理右子树
    cout << node_type; // 输出根结点类型（后序遍历）
}

int main() {
    cin >> n >> s;
    // 字符串长度为2^n
    int len = 1 << n;
    // 给字符串前面加一个空字符，方便前缀和计算（下标从1开始）
    s = " " + s;

    // 计算前缀和数组
    for (int i = 1; i <= len; i++) {
        sum[i] = sum[i - 1] + (s[i] == '1' ? 1 : 0);
    }

    // 递归构造FBI树并输出后序遍历
    dfs(1, len);

    return 0;
}

4.4 代码测试

输入示例：

3
10001011

输出结果：

IBFBBBFIBFIIIFF

这个输出正是 FBI 树的后序遍历序列。通过递归二分字符串并判断类型，我们在构造树的同时完成了后序遍历，既节省了空间（无需显式建树），又体现了递归的简洁性。

五、递归的常见误区与注意事项

通过前面的三个例题，我们已经掌握了递归初阶的核心应用，但在实际使用递归时，还需要注意以下几个常见误区：

5.1 忘记设置递归终止条件

这是最容易犯的错误！如果没有终止条件，函数会无限调用自己，导致栈溢出（Stack Overflow）。比如在汉诺塔问题中，如果去掉if (x == 0) return;，程序会一直递归下去，最终崩溃。

5.2 递归层次过深

递归的调用过程会占用栈空间，而栈的大小是有限的。比如计算n=10000的阶乘时，递归会调用 10000 次，超出栈的容量，导致栈溢出。此时可以用迭代（循环）代替递归，或者使用尾递归优化（部分编译器支持）。

5.3 重复计算子问题

在一些递归问题中，会重复计算相同的子问题，导致时间复杂度飙升。比如斐波那契数列的递归实现：

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

计算fib(5)时，会重复计算fib(3)、fib(2)等子问题。此时可以用记忆化搜索（缓存子问题的解）来优化。

5.4 递归参数传递错误

递归的递推关系依赖于正确的参数传递，比如在汉诺塔的move函数中，中转杆和目标杆的参数顺序错误，会导致移动逻辑混乱。在编写递归函数时，一定要仔细检查参数的含义和传递顺序。

六、递归与迭代的对比

递归和迭代（循环）是解决重复问题的两种主要方式，它们各有优劣：

比如汉诺塔问题用迭代实现会非常复杂，而阶乘问题用迭代实现则更高效。在实际开发中，我们需要根据问题的特点选择合适的方式：如果问题的子问题结构清晰，递归是更好的选择；如果追求性能，迭代通常更优。

总结

递归的学习并非一蹴而就，需要通过大量的练习来加深理解。在后续的学习中，我们还会接触到更复杂的递归问题，比如分治递归、回溯递归等。希望本文能帮助你敲开递归的大门，在算法的世界里继续探索前行！ 最后，送给大家一句话：递归的本质是勇气，敢于把问题交给未来的自己去解决。 当你面对复杂问题时，不妨尝试用递归的思维去拆解它，也许会有意想不到的收获。