企业官网建设流程全解析

前言

在算法竞赛和工程面试里，有三样东西几乎总是同时出现：递归（recursion）、搜索（search）、回溯（backtracking）。初学者常把它们当成三个独立知识点分别去背，结果一遇到"给一个棋盘问有多少种摆法""给你一堆数字问能否凑出目标值"这类题，就不知道从哪个开始想。

真正的原因是：这三者不是并列的三样技术，而是一条链子上的三个环节。

• 
  
• 递归是表达方式：用"自己调用自己"来描述一个规模更小、结构相同的子问题。
• 
  
• 搜索是遍历策略：在由所有可能状态构成的"状态空间树（state space tree）"上，按某种顺序系统地枚举答案。
• 
  
• 回溯是搜索的剪枝机制：走到一条路发现不通时，撤销这一步的选择，退回到分岔口再试另一条。
• 
  
  

一句话：递归是笔，搜索是路，回溯是橡皮擦。本文先把这三样拆开讲透，再用三个完整可运行的例子（迷宫搜索、全排列、N 皇后）把它们合起来用。

一、递归：把大问题交给"另一个自己"

1.1 递归的两个必要条件

一个函数要能正确地递归，必须同时具备：

1. 
   
2. 基准情形（base case）：存在一个足够小的问题规模，其答案可以直接给出，不再递归。
3. 
   
4. 递归情形（recursive case）：能把原问题转化为一个（或多个）规模严格更小的同类问题。
5. 
   
   

缺了基准情形，就是无限递归（infinite recursion），最终栈溢出（stack overflow）。这不是理论风险：Linux 上主线程默认栈大小通常是 8 MB，一个栈帧几十到几百字节，意味着递归深度大约在一万到十万量级就会崩。

1.2 调用栈到底发生了什么

写f(3)时，计算机并不是"跳回去再算一遍"，而是把当前函数的局部变量、参数、返回地址压入调用栈（call stack）——这叫栈帧（stack frame）——再跳转执行；触达基准情形后开始返回，逐层弹出栈帧。所以递归的空间复杂度至少是递归深度，这一点必须刻进直觉里。

// recursion_basic.cpp #include <iostream> #include <vector> // 阶乘：最朴素的线性递归，深度 O(n)，空间 O(n) long long factorial(int n) { if (n <= 1) return 1; // 基准情形 return n * factorial(n - 1); // 递归情形 } // 斐波那契：反面教材，指数级重复计算 O(2^n) long long fib_naive(int n) { if (n <= 1) return n; return fib_naive(n - 1) + fib_naive(n - 2); } // 加上记忆化（memoization），降为 O(n) long long fib_memo(int n, std::vector<long long> &memo) { if (n <= 1) return n; if (memo[n] != -1) return memo[n]; // 已经算过，直接返回 return memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo); } int main() { std::cout << "5! = " << factorial(5) << '\n'; // 120 std::cout << "fib(10) = " << fib_naive(10) << '\n'; // 55 int n = 90; std::vector<long long> memo(n + 1, -1); std::cout << "fib(90) = " << fib_memo(n, memo) << '\n'; return 0; }

注意memo用引用传递（std::vector<long long> &）。如果按值传递，每一层递归都会拷贝整个数组，时间复杂度直接退化成 O(n²) 以上——这是递归中最常见的性能陷阱。任何递归都能改写成迭代（用自己的栈模拟），改写的最大好处是彻底消除爆栈风险，这也是下一篇"递推"的起点。

二、搜索：在状态空间上系统地走

2.1 状态空间树

搜索问题的本质是：把所有可能的"中间状态"组织成一棵树，根是初始状态，每条边是一次决策，叶子是终局，搜索就是按某种顺序遍历这棵树。以"1 到 n 的全排列"为例，根是空序列，第一层决定第一个位置放哪个数，第二层决定第二个……答案在深度为 n 的叶子上。

2.2 两种遍历顺序：DFS 与 BFS

选择口诀：问题问"有多少种方案""是否存在"→ 用 DFS + 回溯；问题问"最少几步""最短距离"→ 用 BFS。

2.3 一个完整的迷宫搜索

地图用字符矩阵表示，S是起点，E是终点，#是墙。

// maze.cpp —— 迷宫：DFS 找一条路，BFS 找最短步数 #include <iostream> #include <queue> #include <string> #include <vector> static const int DR[4] = { -1, 1, 0, 0 }; // 上 下 左 右 static const int DC[4] = { 0, 0, -1, 1 }; int R, C; bool in_bounds(int r, int c) { return r >= 0 && r < R && c >= 0 && c < C; } // ---------- DFS：只关心"能不能到达" ---------- bool dfs(const std::vector<std::string> &g, std::vector<std::vector<bool>> &vis, int r, int c) { if (!in_bounds(r, c) || g[r][c] == '#' || vis[r][c]) return false; if (g[r][c] == 'E') return true; // 找到终点 vis[r][c] = true; // 标记已访问，防止绕圈 for (int d = 0; d < 4; ++d) if (dfs(g, vis, r + DR[d], c + DC[d])) return true; return false; } // ---------- BFS：求从 S 到 E 的最少步数 ---------- int bfs(const std::vector<std::string> &g, int sr, int sc) { std::vector<std::vector<int>> dist(R, std::vector<int>(C, -1)); std::queue<std::pair<int, int>> q; q.push({ sr, sc }); dist[sr][sc] = 0; while (!q.empty()) { auto [r, c] = q.front(); q.pop(); if (g[r][c] == 'E') return dist[r][c]; // 第一次到达即最短 for (int d = 0; d < 4; ++d) { int nr = r + DR[d], nc = c + DC[d]; if (!in_bounds(nr, nc) || g[nr][nc] == '#' || dist[nr][nc] != -1) continue; // 越界 / 墙 / 已访问 dist[nr][nc] = dist[r][c] + 1; // 入队时即确定距离 q.push({ nr, nc }); } } return -1; // 不可达 } int main() { std::vector<std::string> grid = { "S..#......", ".#.#.####.", ".#...#....", ".####.#.#.", "......#..E", }; R = static_cast<int>(grid.size()); C = static_cast<int>(grid[0].size()); std::vector<std::vector<bool>> vis(R, std::vector<bool>(C, false)); std::cout << "DFS reachable : " << (dfs(grid, vis, 0, 0) ? "yes" : "no") << '\n'; std::cout << "BFS min steps : " << bfs(grid, 0, 0) << '\n'; return 0; }

两处决定正确性的细节：

1. 
   
2. BFS 在入队时就把dist确定下来，而不是出队时。同一个节点可能被多个邻居"看到"，如果出队时才写距离，就会出现节点重复入队、距离被覆盖的问题。入队即定距是 BFS 的标准写法。
3. 
   
4. DFS 的vis标记在进入时立刻打上，否则在网格图中会来回横跳，递归永不终止。
5. 
   
   

注意 DFS 这里没有撤销vis。因为问题只问"是否存在一条路径"，走过的格子没必要再走。但只要问题变成"枚举所有路径"，就必须在返回前把vis撤销——这就是第三章要讲的回溯。

三、回溯：选择、尝试、撤销

3.1 回溯的三段式模板

void backtrack(State &s, ...) { if (满足结束条件) { 记录答案; return; } // 1. 边界 for (每个可选的候选 c : 候选集合) { if (!合法(s, c)) continue; // 2. 剪枝 做出选择(s, c); // 3. 进入 backtrack(s, ...); // 深入 撤销选择(s, c); // 4. 恢复现场 ← 灵魂所在 } }

第 4 步"恢复现场"就是回溯区别于普通 DFS 的唯一标志。一句话概括：回溯 = DFS + 状态撤销。

3.2 示例一：全排列

求{1,2,3}的所有排列：每个位置从剩下的数里选一个。

// permutations.cpp #include <iostream> #include <vector> void backtrack(std::vector<int> &nums, std::vector<bool> &used, std::vector<int> &path, std::vector<std::vector<int>> &res) { if (path.size() == nums.size()) { // 边界：每个位置都填满了 res.push_back(path); return; } for (std::size_t i = 0; i < nums.size(); ++i) { if (used[i]) continue; // 剪枝：这个数已经用了 used[i] = true; // 做出选择 path.push_back(nums[i]); backtrack(nums, used, path, res); path.pop_back(); // 撤销选择 used[i] = false; // 恢复现场 } } int main() { std::vector<int> nums = { 1, 2, 3 }; std::vector<bool> used(nums.size(), false); std::vector<int> path; std::vector<std::vector<int>> res; backtrack(nums, used, path, res); for (const auto &p : res) { for (int x : p) std::cout << x << ' '; std::cout << '\n'; } std::cout << "total = " << res.size() << '\n'; // 6 return 0; }

为什么path用引用传递（&）？因为它要在整个递归过程中被共享和修改，"撤销"才有意义。如果按值传，每层都是独立副本，pop_back撤销的是副本，逻辑就散了。

3.3 示例二：N 皇后

在 n×n 棋盘上放 n 个皇后，任意两个不能同行、同列、同对角线。关键优化是用三个布尔数组O(1)判断冲突，而不是每放一个皇后就扫一遍棋盘：

• 
  
• 列冲突：col[c]
• 
  
• 主对角线（左上到右下）：同一条线上r - c是常数，平移后作为下标r - c + n - 1
• 
  
• 副对角线（右上到左下）：同一条线上r + c是常数
• 
  
  

// n_queens.cpp #include <iostream> #include <string> #include <vector> class NQueens { public: explicit NQueens(int n) : n_(n), col_(n, false), diag1_(2 * n, false), diag2_(2 * n, false), board_(n, std::string(n, '.')) {} void solve() const { std::cout << "n = " << n_ << ", solutions = " << count_ << '\n'; } void run() { backtrack(0); } private: void backtrack(int r) { if (r == n_) { // 所有行都摆好了 ++count_; if (n_ <= 6) { // 小棋盘打印出来看 for (const auto &row : board_) std::cout << row << '\n'; std::cout << '\n'; } return; } for (int c = 0; c < n_; ++c) { int d1 = r - c + n_ - 1; int d2 = r + c; if (col_[c] || diag1_[d1] || diag2_[d2]) continue; // 冲突剪枝 board_[r][c] = 'Q'; // 做出选择 col_[c] = diag1_[d1] = diag2_[d2] = true; backtrack(r + 1); board_[r][c] = '.'; // 恢复现场 col_[c] = diag1_[d1] = diag2_[d2] = false; } } int n_; int count_ = 0; std::vector<bool> col_, diag1_, diag2_; std::vector<std::string> board_; }; int main() { for (int n : { 4, 6, 8 }) { NQueens q(n); q.run(); q.solve(); } // n = 4, solutions = 2 / n = 6, solutions = 4 / n = 8, solutions = 92 return 0; }

注意backtrack只需要行号作为参数——列、对角线信息全部编码在布尔数组里。这就是"用状态换时间"：否则每放一个皇后都要遍历已放置的皇后列表检查冲突，N=8 时慢得肉眼可见。

3.4 剪枝：回溯的性能命脉

回溯的时间复杂度是"候选方案的组合数"，暴力枚举往往是指数甚至阶乘级。剪枝（pruning）就是在搜索树还没长全时砍掉无用的分支。

排序剪枝的经典例子——组合总和：从候选数组中选若干个数使和为target，每个数可重复用。排序后一旦nums[i] > remain就break（不是continue，因为后面更大）：

for (std::size_t i = start; i < nums.size(); ++i) { if (nums[i] > remain) break; // ★ 剪枝，break 而非 continue path.push_back(nums[i]); backtrack(nums, i, remain - nums[i], path, res); // 传 i 表示可重用 path.pop_back(); }

把break误写成continue，代码依然能跑出正确结果，但退化成完全枚举，性能天差地别。这类"结果对但慢一万倍"的 bug 最难发现。

常见坑点

坑点 1：忘记恢复现场，答案数量暴涨或凭空减少

❌ 错误写法：

for (int i = 1; i <= n; ++i) { if (used[i]) continue; used[i] = true; path.push_back(i); backtrack(path, n); // ← 这里忘了 path.pop_back(); used[i] = false; }

后果：第一次走到叶子后返回，used全部为true，后续所有分支都被continue掉，只能得到 1 个排列。反过来，若只撤销了used忘了path.pop_back()，path会无限增长，最终因path.size()永远不等于 n 而递归到爆栈。

✅ 正确写法：把"做出选择"和"撤销选择"写成成对出现的两行，中间夹一个backtrack调用，这是唯一能靠肌肉记忆保证不漏的办法。

used[i] = true; path.push_back(i); backtrack(path, n); path.pop_back(); used[i] = false; // ★ 与上面严格对称

坑点 2：递归爆栈

❌ 危险场景：

int dfs(int x) { if (x == 0) return 0; return dfs(x - 1) + 1; } dfs(1000000); // 栈溢出（stack overflow），程序直接崩溃

即使逻辑正确，递归深度一百万也一定会崩：Linux 默认单线程栈约 8 MB，一个栈帧即使只有 64 字节，也只能承受约 13 万层。

✅ 三种正确做法：改成迭代（首选，能写循环就别递归）；用std::stack显式模拟递归，把"栈"搬到堆上；加大栈空间（Linuxulimit -s 65536，Windows 链接时加/STACK:16777216，仅限特定平台）。

还有一个隐蔽的变体——在递归函数里定义大数组：

void dfs(int d) { int buf[1000000]; // 4 MB 栈帧！几层就崩 }

✅ 改成static int buf[1000000];（全局区）或std::vector<int> buf(1000000);（堆区），递归深度就不再受这个数组拖累。

坑点 3：vis标记该不该撤销，搞反了

这是最烧脑的一个坑，取决于问题类型：

❌ 错误写法（枚举所有路径却不撤销）：

vis[r][c] = true; for (int d = 0; d < 4; ++d) if (!vis[nr][nc]) dfs(nr, nc); // 忘了 vis[r][c] = false; → 只能找到一条路径

✅ 正确写法（走到分支末尾时归还）：

vis[r][c] = true; for (int d = 0; d < 4; ++d) if (!vis[nr][nc]) dfs(nr, nc); vis[r][c] = false; // ★ 归还给其它路径使用

判断标准很简单：问自己"这个状态，别的分支还需要用它吗？"需要就撤销，不需要就不撤销。

坑点 4：容器按值传递，撤销失效且疯狂拷贝

❌ 错误写法：

void backtrack(std::vector<int> nums, std::vector<bool> used) { ... }

nums、used都是按值拷贝。每一层递归都复制整个数组，更要命的是：你的pop_back撤销的是副本，父层看到的状态根本没变，逻辑直接崩掉。

✅ 正确写法——需要修改且跨层共享的容器一律传引用：

void backtrack(const std::vector<int> &nums, // 只读 → const 引用 std::vector<bool> &used, // 要改 → 引用 std::vector<int> &path, // 要改 → 引用 std::vector<std::vector<int>> &res) // 收集答案 → 引用

把const加上还有个额外好处：编译器会阻止你在只读参数上误改，很多"忘记撤销"的 bug 会在编译期就被拦下来。

坑点 5：整数溢出把边界条件判断弄失效

搜索中常以"累加和是否等于目标"作为终止条件，如果用int累加：

❌ 危险写法：

int sum = 0; for (int x : nums) sum += x; // nums 里有 1e9 量级的数，累加即溢出 if (sum == target) ...

有符号溢出是未定义行为（undefined behavior），优化器可能把sum == target直接判定为false，程序行为完全不可预测。✅ 更根本的做法是在递归参数里传递剩余目标值remain，而不是每次都重新求和：

void dfs(std::size_t start, long long remain) { if (remain == 0) { /* 记录答案 */ return; } if (remain < 0) return; // 可行性剪枝，顺带防溢出检查 for (std::size_t i = start; i < nums.size(); ++i) { if (nums[i] > remain) break; // 排序后剪枝 path.push_back(nums[i]); dfs(i, remain - nums[i]); // 传下去的是减法，不会越滚越大 path.pop_back(); } }

"传剩余量"而不是"传累加量"，天然规避了溢出，这是搜索题里的一个重要习惯。

坑点 6：BFS 出队时才标记visited，导致重复入队

❌ 错误写法：

while (!q.empty()) { auto cur = q.front(); q.pop(); vis[cur.r][cur.c] = true; // ← 太晚了 for (auto &nb : neighbors(cur)) if (!vis[nb.r][nb.c]) q.push(nb); // 同一个点可能被 push 很多次 }

节点 A 有 5 个邻居同时在队列里，它们出队前都把 A 当作未访问，于是 A 被重复入队 5 次。数据量大时队列会指数级膨胀，内存直接爆炸（MLE）。

✅ 正确写法：入队时立刻标记。

q.push(start); vis[start.r][start.c] = true; // ★ 起点入队即标记 while (!q.empty()) { auto cur = q.front(); q.pop(); for (auto &nb : neighbors(cur)) { if (vis[nb.r][nb.c]) continue; vis[nb.r][nb.c] = true; // ★ 入队前就标记 q.push(nb); } }

坑点 7：递归不记忆化，同一子问题被算了几亿次

❌ 反面教材就是本文开头的fib_naive(50)：

long long fib_naive(int n) { if (n <= 1) return n; return fib_naive(n - 1) + fib_naive(n - 2); // 同一子问题被算了几亿次 }

fib(50)会递归约 2^50 ≈ 10¹⁵ 次调用，实际根本跑不完（fib(40)就要十几秒）。✅ 两条路都有效：记忆化搜索（自顶向下）或递推（自底向上）。

long long fib(int n, std::vector<long long> &memo) { // 路线 A：记忆化 if (n <= 1) return n; if (memo[n] != -1) return memo[n]; return memo[n] = fib(n - 1, memo) + fib(n - 2, memo); }

判断是否该加记忆化的方法：画出递归树，如果发现同一（参数组合）出现了多次，就必须记忆化。这一条也是"回溯"升级为"动态规划（dynamic programming）"的分界线。

总结

把这三个概念重新串一遍：

以及三条可以带走的经验：

1. 
   
2. 递归的空间代价是递归深度。深度可能上万时，要么改迭代，要么把栈搬到堆上；递归函数内绝不放大的局部数组。
3. 
   
4. "做出选择"和"撤销选择"必须成对出现，中间夹一次递归调用。这是回溯不出错的唯一可靠保证。
5. 
   
6. 搜索的性能全在剪枝和状态编码上。用数组把 O(n) 的判断降到 O(1)（N 皇后的三个布尔数组），用排序把"不可能的后续"提前break掉——同一个算法，剪枝与否能差出好几个数量级。
7. 
   
   

最后，递归、搜索、回溯这三剑客之所以总是一起出现，是因为它们共享同一个世界观：把问题看成一棵树，然后决定怎么走、走错了怎么办。想通这一点，这三样就不再是需要分别记忆的三个知识点，而是同一件事的三种说法。