基础
递归:去掉神秘感
一句话答案:递归函数用「同样问题的更小版本」来解决当前问题,并在小到能直接回答的边界处停下。永远两部分:边界条件和递归步。
两部分
#include <iostream>
using namespace std;
long long factorial(int n) {
if (n <= 1) return 1; // 边界:直接回答
return n * factorial(n - 1); // 递归步:更小的问题
}
int main() {
cout << factorial(5) << endl; // 120
return 0;
}去掉边界,函数就一直调用自己,直到程序把栈用光。这种失败有个名字:栈溢出。
实际发生了什么,一步步看
递归不是魔法 —— 是一堆被暂停的调用叠成的栈。每个调用都在等下面那个:
factorial(4)
需要 4 * factorial(3)
需要 3 * factorial(2)
需要 2 * factorial(1)
factorial(1) 返回 1 ← 撞到边界
返回 2 * 1 = 2
返回 3 * 2 = 6
返回 4 * 6 = 24链条向下建立,再向上展开。这就是边界必须可达的原因 —— 否则链条永远不会开始展开。
看得见的递归:倒数
#include <iostream>
using namespace std;
void countdown(int n) {
if (n == 0) { // 边界
cout << "liftoff" << endl;
return;
}
cout << n << " ";
countdown(n - 1); // 递归步
}
int main() {
countdown(5);
return 0;
}注意打印发生在递归调用之前,所以数字是降序。把 cout 移到调用之后,数字就变成升序 —— 这一处顺序调换,就是「下潜之前」和「返回之后」的全部差别。
什么时候递归是自然的工具
只要问题是用自己定义的。汉诺塔是最干净的例子:搬 n 个盘子 = 把 n−1 个挪开、搬最大的、再把 n−1 个挪回来。
#include <iostream>
using namespace std;
void hanoi(int n, int from, int to, int via) {
if (n == 0) return;
hanoi(n - 1, from, via, to);
cout << "move " << n << " from " << from << " to " << to << endl;
hanoi(n - 1, via, to, from);
}
int main() {
hanoi(3, 1, 3, 2);
return 0;
}手推一次看看。你会发现你不需要把整个序列装进脑子才能相信这段代码 —— 你只需要相信两个更小的调用是对的。这就是递归要求的思维动作,练习题汉诺塔练的正是它。
递归 vs 循环
任何递归都能改写成带显式栈或累加器的循环。怎么选:
| 用递归,当… | 用循环,当… |
|---|---|
| 问题天然自相似(树、分治) | 只是对一个范围简单重复 |
| 深度很小(几十层,不是几百万层) | 深度可能极大 |
| 代码明显更短更清楚 | 递归版本反正也要自己维护栈 |
代价
- 栈空间。每个未完成的调用都占一帧。深度一百万会崩;深度 40 什么都不算。
- 重复计算。朴素递归斐波那契每层调用自己两次 —— 约 2^n 次。斐波那契展示了修法(带两个值走)。
- 边界必须可达。会跳过边界的步进(边界判 n == 0,却写 n -= 2)照样溢出。
面试追问
- 什么是栈溢出?嵌套调用太多,调用栈没空间了。几乎总是边界缺失或不可达。
- 怎么把这段递归改成循环?找出累加器和方向;树状递归需要显式维护一个栈。
- 为什么朴素斐波那契是指数级?因为它重复计算同样的子问题 —— 备忘录或自底向上 DP 的经典案例。