一、递归的概念
递归是函数直接或间接调用自身的一种编程技巧。核心思想是将大问题分解为相似的小问题。递归函数通常包含两部分:基线条件(停止递归的条件)和递归条件(继续调用自身的条件)。
如果还不太理解,什么是基线条件?
(也叫基本条件):就是'不用递归也能直接求出的条件'或者说'递归可以直接给出答案而不需要进一步调用的最简单情况'。
二、适合新手的递归示例
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;
;
}
(n - , source, target, auxiliary);
cout << << n << << source << << target << endl;
(n - , auxiliary, source, target);
}
{
num_disks = ;
(num_disks, , , );
;
}



