一、递归到底是什么？
递归的核心是一个函数自己调用自己，像镜子照镜子、俄罗斯套娃一样。写递归必须记两个关键点：
递归出口：什么时候停下来，没有出口程序会无限循环；
递归关系：把大问题拆成更小的同类型问题。
二、递归入门例子
例子 1：递归求 1+2+…+n 的和
cpp
#include <iostream>
using namespace std;
int s(int n) {
if (n == 1) {
return 1;
}
return n + s(n - 1);
}
int main() {
cout << s(5) << endl;
return 0;
}
例子 2：递归求 n!（阶乘）
cpp
#include <iostream>
using namespace std;
int f(int n) {
if (n == 1) {
return 1;
}
return n * f(n - 1);
}
int main() {
cout << f(5) << endl;
return 0;
}
例子 3：递归输出倒序数字
cpp
#include <iostream>
using namespace std;
void p(int n) {
if (n == 0) {
return;
}
cout << n << " ";
p(n - 1);
}
int main() {
p(5);
return 0;
}
三、递归经典小题目
题目 1：爬楼梯
cpp
#include <iostream>
using namespace std;
int c(int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
return c(n - 1) + c(n - 2);
}
int main() {
cout << c(4) << endl;
return 0;
}
题目 2：递归求最大公约数
cpp
#include <iostream>
using namespace std;
int g(int a, int b) {
if (b == 0) {
return a;
}
return g(b, a % b);
}
int main() {
cout << g(12, 18) << endl;
return 0;
}
四、递归踩坑记录
忘记写递归出口，程序直接卡死；
递归关系写错，比如把 “+” 写成 “×”，答案全错；
参数传错，把 n-1 写成 n+1，递归停不下来；
递归层数太多，程序会 “爆栈” 崩溃。
