一、递归的概念
递归是函数直接或间接调用自身的一种编程技巧。核心思想是将大问题分解为相似的小问题。递归函数通常包含两部分：基线条件（停止递归的条件）和递归条件（继续调用自身的条件）。
如果还不太理解，什么是基线条件？
（也叫基本条件）：就是'不用递归也能直接求出的条件'或者说'递归可以直接给出答案而不需要进一步调用的最简单情况'。
二、适合新手的递归示例
1. 阶乘计算
阶乘（n!）是经典的递归案例，定义如下：
基线条件：0! = 1 1! = 1 (0 和 1 的阶乘不用求也知道是 1) 递归条件：n! = n × (n-1)!
2. 斐波那契数列
斐波那契数列（0, 1, 1, 2, 3, 5…）中每个数是前两数之和：
基线条件：fib(0) = 0, fib(1) = 1 (前两个数题目一定会给出) 递归条件：fib(n) = fib(n-1) + fib(n-2)
3. 汉诺塔问题（较难）
汉诺塔问题概述
汉诺塔（Tower of Hanoi）是一个经典的递归问题，源于一个传说。问题描述为：有三根柱子，其中一根柱子上有若干大小不一的圆盘，圆盘按大小顺序叠放，小的在上，大的在下。目标是将所有圆盘移动到另一根柱子上，且在移动过程中任何时候都不能将大的圆盘放在小的圆盘上。
递归解法思路
递归的核心思想是将问题分解为更小的子问题。对于汉诺塔问题，可以将移动 n 个圆盘的任务分解为：
- 将 n-1 个圆盘从起始柱移动到辅助柱。
- 将第 n 个圆盘（最大的圆盘）从起始柱移动到目标柱。
- 将 n-1 个圆盘从辅助柱移动到目标柱。
#include <bits/stdc++.h>
using namespace std;
void hanoi(int n, char source, char auxiliary, char target) {
if (n == 1) {
// 处理最底层的情况：当只剩下 1 个盘子时
cout << "Move disk 1 from " << source << " to " << target << endl;
return;
}
// 步骤 1：把上面 n-1 个盘子从起始柱借助目标柱移到辅助柱
hanoi(n - 1, source, target, auxiliary);
cout << "Move disk " << n << " from " << source << " to " << target << endl;
// 步骤 2.处理当前层的情况：移动当前最大的盘子
// 步骤 3：把 n-1 个盘子从辅助柱借助起始柱移到目标柱
hanoi(n - 1, auxiliary, source, target);
}
int main() {
int num_disks = 3; // 圆盘数量
hanoi(num_disks, 'A', 'B', 'C');
return 0;
}
代码解析
- hanoi 函数接受四个参数：圆盘数量 n、起始柱 source、辅助柱 auxiliary 和目标柱 target。
- 当 n == 1 时，直接移动圆盘到目标柱。
- 对于 n > 1，递归调用 hanoi 函数分解问题。
示例输出
对于 3 个圆盘，输出如下：
Move disk 1 from A to C Move disk 2 from A to B Move disk 1 from C to B Move disk 3 from A to C Move disk 1 from B to A Move disk 2 from B to C Move disk 1 from A to C
应用场景
汉诺塔问题不仅是递归算法的经典案例，还常用于教学和面试中，帮助理解递归和分治思想。
三、新手常见问题
1. 缺少基本情况（无限递归）
问题表现
// 错误示例：忘记写基本情况
int factorial(int n) {
return n * factorial(n - 1); // 没有停止条件！
}
int main() {
cout << factorial(5); // 导致栈溢出！
return 0;
}
正确写法
int factorial(int n) {
if (n <= 1) return 1; // ← 必须有的基本情况
return n * factorial(n - 1);
}
2. 基本情况不完整
问题表现
// 错误示例：只考虑了一种基本情况
int fibonacci(int n) {
if (n == 0) return 0; // 只考虑了 n=0，忘记了 n=1
return fibonacci(n-1)+fibonacci(n-2); // n=1 时会无限递归
}
int main() {
cout << fibonacci(1); // 栈溢出！
return 0;
}
正确写法
int fibonacci(int n) {
if (n == 0) return 0;
if (n == 1) return 1; // ← 需要多个基本情况
return fibonacci(n-1)+fibonacci(n-2);
}
3. 递归深度太大导致栈溢出
问题表现
// 错误示例：深度太大
int sum(int n) {
if (n == 0) return 0;
return n + sum(n - 1);
}
int main() {
cout << sum(1000000); // 递归太深，栈溢出！
return 0;
}
解决方案
// 使用迭代代替递归（用循环代替递归调用）
int sumIterative(int n) {
int result = 0;
for (int i = 1; i <= n; i++) {
result += i;
}
return result;
}
四、样例升级
1. 爬楼梯（最多一次走两级）
分析： 1 级：1 2 级：1，2 3 级：1，1+2，2+1 4 级：1，2，1+2+1，2+1+1，1+1+2 5 级：1，1+1+1+2，1+1+2+1，2+1+1+1，1+2+1+1，1+2+2，2+1+2，2+2+1 6 级…
//解释 例如 3 级：1 步一步上，先 1 步再 2 步，先 2 步再 1 步 总结： 1 级 一种方法 2 级 2 种 3 级 3 种 4 级 5 种 5 级 8 种 … 5 级的方法数=（3 级 +4 级）的方法数 所以 n 级的方法数=（n-1）+(n-2)
代码如下：
//这与斐波那契数列类似。
