C++ 递归函数完全指南

模块 01

情景导航

先用"俄罗斯套娃"的故事建立递归的直觉，再用生活类比看清"自我调用"的本质，最后给出递归函数的准确定义和一句好记的口诀。

故事故事引入 —— 俄罗斯套娃

小强在超市看到一套俄罗斯套娃，最大的里面套着一个中等的，中等的里面套着一个小的，最小的那个打开一看，里面什么都没有——只有一张纸条写着"到此为止"。

小强好奇地数了一下：最大的算第 1 层，中等的算第 2 层，最小的算第 3 层，一共 3 层。他问妈妈："如果每层套娃都比上一层小一圈，那最里面那层'没有套娃'的算不算一层？"

妈妈笑着说："当然算！没有最里面那层'到此为止'，套娃就永远套不完啦。"

"一层套一层，直到碰到'最小的那个'就停 —— 套娃就是递归！"

老师笑着揭秘：程序里也有这种"一层套一层"的写法，函数自己调用自己，就叫递归函数。但和套娃一样，递归也必须有一个"最里面"的终点，否则就会永远套下去，程序就卡死了。

💡 这个故事告诉我们什么？

套娃有三个特点，也正是递归函数的三个关键：

一、每一层都"套着下一层"（函数调用自己）；二、越套越小，最终会碰到"最小的那个"（基准情况，递归终止）；三、套完之后，每一层都"把结果传回来"（返回值层层返回）。

程序里的递归函数也是如此：自己调用自己，逐步缩小问题规模，直到碰到最简单的情况直接返回结果，然后层层返回，最终得到答案。

类比生活类比 —— 套娃、镜子、查字典与借书

把递归的四种场景和身边的东西对一对号，递归逻辑一下子就清晰了：

🛣

俄罗斯套娃 · 一层套一层

大娃套中娃，中娃套小娃，最小娃里写着"到此为止"。程序里函数调用自己，直到碰到基准情况停止。

对应：递归函数的自我调用

🧥

两面镜子 · 无限反射

两面镜子面对面放，里面会出现无数个自己的倒影。如果没有"最后一面镜子"挡住，反射就永远不停。这就是没有基准情况的递归——死循环！

对应：缺少基准情况的递归（死递归）

📖

查字典 · 遇到不懂的词查释义

查"递归"这个词，释义里又出现了"递归"，于是再查一次。直到查到最简单的词（如"函数"），直接读懂，再回头理解前面的词。

对应：递归展开 + 层层返回

📚

借书 · 借不到就找下一本

想借第 n 本书，图书馆说"借完了"，于是借第 n-1 本；如果第 1 本也没了，那就去书店买一本（基准情况），再依次借给后面的人。

对应：递归的"向下探索 + 向上返回"

定义什么是递归函数

到目前为止我们学的函数都是"别人叫它，它才执行"——main 调用它，或者另一个函数调用它。但 C++ 允许函数自己调用自己，这种函数就叫递归函数。

结构名称	执行方式	本课关键词
普通函数	被其他函数调用后执行一次	定义 + 调用（第 3 讲）
递归函数	函数体内部调用自己，直到满足终止条件	递归 = 自己调自己（本课）
循环（for/while）	重复执行某段代码直到条件不满足	计数器控制（第 4 讲）

递归函数的准确定义：一个函数在它的函数体内部直接或间接地调用自身，并且在某一步会直接返回一个确定的值（不再继续调用自己），这样的函数就叫递归函数。

递归不是"无限循环"，它有两个缺一不可的要素：基准情况（Base Case）—— 直接返回结果，不再递归；递归步骤（Recursive Step）—— 把问题缩小后调用自己。没有基准情况，递归就会永远进行下去，就像两面镜子面对面放，倒影永远出不来。

递归函数口诀递归函数自己叫，缩小问题往下跑；
基准情况直接返，不叫自己停住了；
层层返回结果到，栈帧展开像套娃；
忘了基准会死循环，写递归时先想停。

口诀里藏着本课的全部主角：自己调用自己、缩小问题、基准情况、层层返回。下面我们就把它们一个一个请出来，看清递归的"内部构造"和执行路线。

模块 02

知识探究

逐一拆解递归的两个要素（基准情况 + 递归步骤）、调用栈执行过程、阶乘与斐波那契数列、递归与循环的对比，再看 6 个由浅入深的案例把递归写法一次练熟。

1递归的两个要素 —— 基准情况 + 递归步骤

递归函数看起来很简单——函数自己调用自己。但写起来却很容易"死循环"。关键在于，递归必须有两个要素，缺一不可：

递归函数 { if (基准情况) return 值; return 递归调用(缩小后的问题); }

递归函数：自己调自己的函数基准情况：问题足够小时直接返回递归步骤：缩小问题后调用自己

要素	作用	类比
基准情况（Base Case）	问题足够小时直接返回结果，不再递归。是递归的"终点"。	套娃里最小的那个，打开就停
递归步骤（Recursive Step）	把问题缩小一点，然后调用自己。是递归的"过程"。	把大娃打开，交给小娃去处理

一句话记住：基准情况说"到此为止"，递归步骤说"把小一点的问题交给下一层"。没有"到此为止"，递归就永远停不下来；没有"交给下一层"，递归就永远做不了事。

2调用栈执行过程 —— 函数是怎么"记住"自己的

每次函数被调用，系统都会在调用栈（Call Stack）上压入一个"栈帧"，记录这个函数的参数和局部变量。递归调用自己时，每一层都有自己的独立栈帧，互不干扰。

阶段	栈帧状态	说明
展开阶段（向下）	每调用一次，压入一个新栈帧	参数逐步缩小，直到碰到基准情况
基准情况	直接返回一个值，不再压栈	递归的终点，栈帧开始弹出
回溯阶段（向上）	每弹出一个栈帧，带回一个返回值	层层返回，直到回到最初的调用

展开阶段（向下）

fact(5) → 调用 fact(4)
fact(4) → 调用 fact(3)
fact(3) → 调用 fact(2)
fact(2) → 调用 fact(1)
fact(1) → 返回 1（基准情况！）

回溯阶段（向上）

fact(1) 返回 1
fact(2) = 2 × 1 = 2
fact(3) = 3 × 2 = 6
fact(4) = 4 × 6 = 24
fact(5) = 5 × 24 = 120

形象理解：调用栈就像一摞盘子，每次调用自己就往栈顶放一个新盘子（展开），碰到基准情况后，每吃完一个盘子就把它拿走（回溯），最后栈空了，程序结束。

3阶乘函数 —— 递归的第一课

阶乘（factorial）是递归最经典的入门案例。n! = n × (n-1) × (n-2) × ... × 1，其中 0! = 1。

阶乘天然适合递归：n! = n × (n-1)!，也就是说，求 n 的阶乘，只需要把 n 乘上 (n-1) 的阶乘。而 (n-1)! 又等于 (n-1) × (n-2)!，层层递推，直到 0! = 1（基准情况）。

C++阶乘递归函数

#include <iostream>
using namespace std;
long long factorial(int n) {
    if (n == 0 || n == 1) {       // 基准情况
        return 1;
    }
    return n * factorial(n - 1);   // 递归步骤
}
int main() {
    int n;
    cin >> n;
    cout << n << "! = " << factorial(n) << endl;
    return 0;
}

运行结果

输入：5
输出：5! = 120

解读：调用 factorial(5) 时，n=5 不是 0 或 1，所以返回 5 × factorial(4)。这又调用 factorial(4)，返回 4 × factorial(3)……直到 factorial(1) 碰到基准情况，直接返回 1。然后层层回溯：1 → 2 → 6 → 24 → 120。

4斐波那契数列 —— 两个基准情况的递归

斐波那契数列（Fibonacci）是递归的另一个经典案例。数列定义为：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)（n≥2）。

这个数列的前几项是：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... 每一项都是前两项之和。

C++斐波那契递归函数

#include <iostream>
using namespace std;
int fibonacci(int n) {
    if (n == 0) return 0;        // 基准情况 1
    if (n == 1) return 1;        // 基准情况 2
    return fibonacci(n - 1) + fibonacci(n - 2);  // 递归步骤
}
int main() {
    int n;
    cin >> n;
    cout << "F(" << n << ") = " << fibonacci(n) << endl;
    return 0;
}

运行结果

输入：10
输出：F(10) = 55

解读：斐波那契有两个基准情况（n=0 返回 0，n=1 返回 1）。当 n=10 时，递归会展开成一棵"调用树"，每一层分裂成两个子调用，直到 n 缩小到 0 或 1。这也是递归效率较低的一个典型例子——后面会对比循环写法。

5递归 vs 循环 —— 怎么选

递归擅长

问题天然可以拆成相同子问题（阶乘、斐波那契、树遍历）
代码简洁、逻辑清晰、容易理解
分治算法、回溯算法、动态规划
递归深度不大时（通常 < 1000）

循环擅长

简单的重复计算（求和、排序、查找）
对性能要求高的场景
递归深度可能很大时（避免栈溢出）
斐波那契用循环只需 O(n) 时间，递归会重复计算

对比项	递归	循环
代码可读性	高（逻辑直观）	中（需要自己管理状态）
执行效率	较低（函数调用开销 + 可能重复计算）	较高（直接跳转）
空间消耗	较大（每层调用占用栈帧）	较小（只需几个变量）
栈溢出风险	有（递归太深会栈溢出）	无
适用场景	树/图遍历、分治、回溯	简单重复、数值计算

选择要诀：先想清楚"基准情况"和"递归步骤"，如果问题天然可以拆成相同子问题，用递归写起来最优雅；如果递归深度可能很大，或者性能要求高，用循环更高效。

6串起来看：fact(5) 的完整执行旅程

把阶乘递归函数跑一遍：输入 5，看程序如何层层展开、又层层返回。

🎬 动画演示：fact(5) 的调用栈变化

调用 factorial(5) —— n=5，不是基准情况，进入递归步骤

调用 factorial(4) —— n=4，不是基准情况，继续递归

调用 factorial(3) —— n=3，不是基准情况，继续递归

调用 factorial(2) —— n=2，不是基准情况，继续递归

调用 factorial(1) —— n=1，碰到基准情况！直接返回 1

回溯：factorial(2) = 2 × 1 = 2

回溯：factorial(3) = 3 × 2 = 6

回溯：factorial(4) = 4 × 6 = 24

回溯：factorial(5) = 5 × 24 = 120，程序输出 120

解读：递归的执行分两个阶段：展开阶段（从 fact(5) 到 fact(1)，不断调用自己）和 回溯阶段（从 fact(1) 返回 1，层层计算乘法）。记住：基准情况是"转折点"，没有它，展开就永远不会变成回溯。

案例6 个由浅入深的案例

案例 1：阶乘函数 —— 递归的"Hello World"

题目：写一个递归函数 factorial(n)，计算 n!。读入 n，输出结果。

C++阶乘递归

#include <iostream>
using namespace std;
long long factorial(int n) {
    if (n == 0 || n == 1) return 1;
    return n * factorial(n - 1);
}
int main() {
    int n; cin >> n;
    cout << n << "! = " << factorial(n) << endl;
    return 0;
}

运行结果

输入：5
输出：5! = 120

解读：基准情况是 n=0 或 n=1 时返回 1；递归步骤是 n × factorial(n-1)。每次调用 n 减小 1，最终一定会到达基准情况。

案例 2：斐波那契数列 —— 两个基准情况的递归

题目：写一个递归函数 fibonacci(n)，计算第 n 项斐波那契数。F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)。

C++斐波那契递归

#include <iostream>
using namespace std;
int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}
int main() {
    int n; cin >> n;
    cout << "F(" << n << ") = " << fibonacci(n) << endl;
    return 0;
}

运行结果

输入：10
输出：F(10) = 55

解读：两个基准情况（n=0 和 n=1），递归步骤分裂成两个子调用。注意：这种写法效率较低，因为会重复计算相同的子问题（如 fibonacci(3) 会被算很多次）。后面会学到用循环优化。

案例 3：递归求和 —— 从 1 加到 n

题目：写一个递归函数 sum(n)，计算 1+2+...+n 的和。

C++递归求和

#include <iostream>
using namespace std;
int sum(int n) {
    if (n == 1) return 1;       // 基准情况
    return n + sum(n - 1);       // 递归步骤：n + (1+...+(n-1))
}
int main() {
    int n; cin >> n;
    cout << "1+...+" << n << " = " << sum(n) << endl;
    return 0;
}

运行结果

输入：100
输出：1+...+100 = 5050

解读：sum(100) = 100 + sum(99) = 100 + 99 + sum(98) = ... = 100 + 99 + ... + 1。基准情况是 n=1 返回 1，递归步骤是 n + sum(n-1)。

案例 4：递归打印数组 —— 从后往前输出

题目：写一个递归函数 printArray(arr, n)，先递归到末尾，回溯时打印（正序输出）的前 n 个元素。

C++递归打印数组

#include <iostream>
using namespace std;
void printArray(int arr[], int n) {
    if (n <= 0) return;          // 基准情况
    printArray(arr, n - 1);         // 先递归处理前 n-1 个
    cout << arr[n - 1] << " ";    // 再打印当前元素
}
int main() {
    int arr[] = {1, 2, 3, 4, 5};
    printArray(arr, 5);
    cout << endl;
    return 0;
}

运行结果

1 2 3 4 5

解读：这个函数先递归到 n=0（基准情况），然后回溯时逐层打印。因为先递归再打印，所以输出顺序是正序。如果把打印和递归的顺序调换（先打印再递归），就会变成倒序输出。

案例 5：递归求幂 —— a 的 n 次方

题目：写一个递归函数 power(a, n)，计算 a 的 n 次方（a^n）。

C++递归求幂

#include <iostream>
using namespace std;
long long power(double a, int n) {
    if (n == 0) return 1;         // 基准情况：a^0 = 1
    return a * power(a, n - 1);   // 递归步骤：a^n = a * a^(n-1)
}
int main() {
    double a; int n;
    cin >> a >> n;
    cout << a << "^" << n << " = " << power(a, n) << endl;
    return 0;
}

运行结果

输入：2.0 10
输出：2^10 = 1024

解读：基准情况是 n=0 返回 1（任何数的 0 次方都是 1）。递归步骤是 a × power(a, n-1)。每次 n 减小 1，最终到达 n=0。

案例 6：现场捉虫 —— 三处经典错误

题目：下面这段代码藏着 3 处递归高频错误，先自己找一找。

C++待捉虫的代码

int factorial(int n) {
    // 第 1 处：缺少基准情况
    return n * factorial(n - 1);
}
int sum(int n) {
    if (n == 1) return 1;
    return n + sum(n);    // 第 2 处：参数没有缩小
}
int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}
int main() {
    cout << fib(-3) << endl;  // 第 3 处：传入负数
    return 0;
}

点击查看捉虫结果

第 1 处：factorial 函数缺少基准情况。没有 if 判断 n 是否到达终点，会无限递归调用自己，最终导致栈溢出（Stack Overflow）崩溃。必须加上 if (n == 0 || n == 1) return 1;。

第 2 处：sum 函数的递归步骤写成了 sum(n)，参数没有缩小！应该写成 sum(n-1)。否则每次调用都传同样的 n，永远到不了基准情况 n=1，同样导致栈溢出。

第 3 处：fib(-3) 传入负数。fib 的基准情况是 n<=1 返回 n，所以 fib(-3) 会直接返回 -3。但如果传入负数后递归步骤继续减小（n-1 和 n-2），就会越来越小，永远碰不到基准情况。调用 fib 前应该先检查参数是否合法。

要点	说明
递归 = 自己调自己	函数在函数体内部调用自身
基准情况（Base Case）	问题足够小时直接返回，是递归的"终点"。没有它 = 死递归
递归步骤（Recursive Step）	把问题缩小后调用自己，参数必须朝着基准情况方向变化
调用栈（Call Stack）	每层调用有自己的栈帧，展开阶段向下压栈，回溯阶段向上弹栈
递归 vs 循环	递归代码简洁但效率低；循环效率高但代码稍复杂。递归深度大时用循环
递归深度限制	一般递归深度不超过几千层，否则栈溢出（Stack Overflow）

步骤	操作
第 1 步	把上面 n-1 个盘子从 A 借助 C 移到 B
第 2 步	把最底下的第 n 个盘子从 A 直接移到 C
第 3 步	把 B 上的 n-1 个盘子借助 A 移到 C

模块 05

学习检测

5 个最容易丢分的递归陷阱、一张考前必背速查表，以及可以贴在文具盒上的知识点速记卡。

易错 1

忘记写基准情况（Base Case）

递归函数没有基准情况，就会无限调用自己，最终导致栈溢出（Stack Overflow），程序崩溃。

错误写法

int fact(int n) {
    return n * fact(n - 1);
}

正确写法

int fact(int n) {
    if (n <= 1) return 1;
    return n * fact(n - 1);
}

口诀：写递归先想停，基准情况不能丢；没有停的点，程序就崩溃。

易错 2

递归步骤参数没有缩小

递归步骤的参数必须朝着基准情况的方向变化。如果参数不变或反向变化，就永远到不了基准情况。

错误写法

int sum(int n) {
    if (n == 1) return 1;
    return n + sum(n);
}

正确写法

int sum(int n) {
    if (n == 1) return 1;
    return n + sum(n - 1);
}

口诀：递归调用参数变，朝着基准方向走；参数不变就死循环，栈溢出等着你。

易错 3

基准情况漏写或多写

基准情况必须覆盖所有"问题足够小"的输入。漏写会导致某些输入无法终止。

漏写基准

int fib(int n) {
    if (n == 1) return 1;
    return fib(n-1) + fib(n-2);
}

补全基准

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

口诀：基准情况要想全，边界输入都覆盖；漏掉一个边界，程序就崩溃。

易错 4

递归深度过大导致栈溢出

每次函数调用都要在栈上分配空间。递归太深（通常超过几千层），栈空间不够用，就会栈溢出（Stack Overflow），程序崩溃。

说明

栈溢出：递归深度太大，调用栈空间耗尽。常见于递归没有正确终止或递归树太大。

解决方法

1 改用循环；2 记忆化搜索（缓存已计算结果）；3 动态规划（自底向上）。

口诀：递归太深会崩溃，栈空间就那么多；改循环或加缓存，效率翻倍不报错。

易错 5

混淆"展开"和"回溯"的执行顺序

递归调用前后的语句执行顺序完全不同。调用前的语句在"展开阶段"执行（从大到小），调用后的语句在"回溯阶段"执行（从小到大）。

先打印再递归

void f(int n) {
    cout << n << " ";
    if (n > 1) f(n-1);
}

先递归再打印

void f(int n) {
    if (n > 1) f(n-1);
    cout << n << " ";
}

口诀：递归前写的先执行（从大到小），递归后写的后执行（从小到大）。想正序还是倒序，看打印写在哪边。

速查考前速查表

概念	写法	特点	示例	提醒
递归函数	int f(n) { if(基准) return; return f(缩小); }	自己调自己	return n * f(n-1);	必须有基准情况
基准情况	if (n == 0) return 1;	直接返回，不递归	if (n <= 1) return n;	覆盖所有边界
递归步骤	return f(n-1) + ...;	缩小问题后调用	return f(n-1) + f(n-2);	参数必须缩小
调用栈	展开→基准→回溯	先压后弹	fact(5)→fact(1)→返回	每层独立栈帧
递归 vs 循环	递归优雅/效率低	看场景选	斐波那契用循环更快	深度大时改循环
栈溢出	递归太深崩溃	空间不够	n=10000 的递归可能溢出	改循环或记忆化

📌知识点速记卡

递归 = 自己调自己

函数在函数体内部调用自身，把大问题拆成相同的小问题。

两个要素缺一不可

基准情况（终点）+ 递归步骤（缩小问题）。没有基准 = 死递归。

展开阶段向下，回溯阶段向上

碰到基准情况后开始返回，每层带回一个结果，直到回到最初调用。

参数必须朝基准方向变化

每次递归调用，参数必须更接近基准情况，否则永远停不下来。

调用栈 = 一摞盘子

每层调用有自己的栈帧（参数和局部变量），互不干扰。栈满就溢出。

递归深度有限制

一般几千层是安全范围。太深就改循环或用记忆化搜索优化。

递归调用前后的语句顺序不同

调用前的语句先执行（展开），调用后的语句后执行（回溯）。

斐波那契递归效率低

会重复计算相同子问题。用循环或记忆化可将 O(2^n) 降到 O(n)。

课后练习

练习作业

巩固递归函数的定义、基准情况与递归步骤的写法，分层练习，点击展开答案与解析。

总结练习3 道综合题

总结 1判断题

题目：判断 —— 递归函数必须有且只有一个基准情况。

提示：想想斐波那契数列的递归函数有几个基准情况。

点击查看参考答案

答案：错误。递归函数可以有多个基准情况。例如斐波那契数列有两个基准情况：F(0)=0 和 F(1)=1。关键是"至少有一个"，且所有可能的终止输入都必须被覆盖。

总结 2写输出

题目：下面程序输出什么？

C++递归追踪

#include <iostream>
using namespace std;
int f(int n) {
    if (n == 0) return 0;
    return n + f(n - 1);
}
int main() {
    cout << f(5) << endl;
    return 0;
}

点击查看参考答案

答案：15。f(5) = 5 + f(4) = 5 + 4 + f(3) = ... = 5 + 4 + 3 + 2 + 1 + f(0) = 5 + 4 + 3 + 2 + 1 + 0 = 15。这就是 1 到 5 的和。

总结 3编程题

题目：写一个递归函数 reverse(n)，将一个正整数的各位数字倒序输出。例如 reverse(123) 输出 321。

提示：基准情况是 n < 10 时直接打印；递归步骤是先打印 n%10，再递归处理 n/10。

点击查看参考答案

C++参考代码

#include <iostream>
using namespace std;
void reverse(int n) {
    if (n < 10) { cout << n; return; }
    cout << n % 10;
    reverse(n / 10);
}
int main() {
    int n; cin >> n;
    reverse(n);
    cout << endl;
    return 0;
}

示例：输入 123 → 输出 321。reverse(123) 先打印 3，再递归 reverse(12) 打印 2，再递归 reverse(1) 打印 1。

A 组基础巩固（4 题）

A1填空题

题目：递归函数必须有两个要素：（直接返回结果，不再递归）和（缩小问题后调用自己）。

点击查看参考答案

C++完整参考代码

#include <iostream>
using namespace std;

int fact(int n) {
    if (n == 1) return 1;          // 基准情况：直接返回结果，不再递归
    return n * fact(n - 1);        // 递归步骤：把问题缩小后调用自己
}

int main() {
    cout << fact(5) << endl;       // 5×4×3×2×1 = 120
    return 0;
}

// 运行结果：120

答案：基准情况（Base Case）；递归步骤（Recursive Step）。

思路：基准情况是递归的出口，告诉函数「到这一步直接给答案，不用再往下叫自己」；递归步骤负责把大问题切成小一号的问题，再交给同一函数去解决。

考点：递归函数的两大要素，两者缺一不可。

易错：只写递归步骤、忘了基准情况——函数永远找不到出口，会一直调用下去直到栈溢出（奔溃）。

A2判断题

题目：判断 —— 递归函数调用自己时，每一层都有自己的参数和局部变量，互不影响。

点击查看参考答案

答案：正确。每次函数调用都会在调用栈上创建一个新的栈帧，包含该次调用的参数和局部变量。不同层的变量互不干扰，这就是递归能正确工作的基础。

考点：递归调用栈——每次调用在栈上新建栈帧，各层的参数和局部变量互相独立。

易错：误以为递归各层共享同一个变量，手动模拟时就会算错。

A3写输出

题目：下面程序输出什么？

C++阶乘追踪

#include <iostream>
using namespace std;
int fact(int n) {
    if (n == 1) return 1;
    return n * fact(n - 1);
}
int main() {
    cout << fact(4) << endl;
    return 0;
}

点击查看参考答案

C++完整参考代码

#include <iostream>
using namespace std;

int fact(int n) {
    if (n == 1) return 1;          // 基准情况
    return n * fact(n - 1);        // 递归步骤
}

int main() {
    cout << fact(4) << endl;       // 4×3×2×1 = 24
    return 0;
}

// 运行结果：24

答案：24。

思路：fact(4) = 4 × fact(3) = 4 × 3 × fact(2) = 4 × 3 × 2 × fact(1) = 4 × 3 × 2 × 1 = 24，正好是 4! = 24。

考点：递归的展开与回溯过程，以及阶乘的递归定义。

易错：把基准情况当成 n == 0——本题写的是 n == 1，最后乘到 1 就停下；若改成 n == 0，结果一样但会多算一层。

A4编程题

题目：写一个递归函数 power(a, n)，计算 a 的 n 次方（a^n），其中 n 是非负整数。

提示：基准情况是 n=0 时返回 1；递归步骤是 a × power(a, n-1)。

点击查看参考答案

C++完整参考代码

#include <iostream>
using namespace std;

// 计算 a^n，n 为非负整数
long long power(long long a, int n) {
    if (n == 0) return 1;              // 基准情况：a^0 = 1
    return a * power(a, n - 1);        // 递归步骤：a^n = a × a^(n-1)
}

int main() {
    cout << power(2, 10) << endl;      // 1024
    cout << power(3, 0) << endl;       // 1
    cout << power(5, 3) << endl;       // 125
    return 0;
}

// 运行结果：
// 1024
// 1
// 125

答案：用递归定义：n == 0 时返回 1（基准情况），否则返回 a * power(a, n-1)（递归步骤）。完整程序见左侧代码。

思路：a^n = a × a × … × a（共 n 个）。先处理最简单的情形 a^0 = 1，再让每一层负责乘一个 a，把指数减 1 交下去，直到指数变成 0 停下。实测 power(2,10) = 1024，power(3,0) = 1，power(5,3) = 125。

考点：基准情况取 n == 0（而不是 n == 1），因为「0 个 a 相乘」必须定义成 1，否则 a^0 就没法算了。

易错：示例签名写成 int power(double a, int n)——返回类型和参数类型不一致，小数底数会被截断成整数。底数是什么类型，返回类型就跟着用什么类型（这里用 long long 防溢出）。

B 组能力提高（4 题）

B1写输出

题目：下面程序输出什么？

C++递归打印

#include <iostream>
using namespace std;
void f(int n) {
    if (n <= 0) return;
    f(n - 1);
    cout << n << " ";
}
int main() {
    f(5);
    cout << endl;
    return 0;
}

点击查看参考答案

C++完整参考代码

#include <iostream>
using namespace std;

void f(int n) {
    if (n <= 0) return;      // 基准情况：n 减到 0 就返回
    f(n - 1);                // 先一路递归到底
    cout << n << " ";        // 回溯阶段才打印，所以是正序
}

int main() {
    f(5);
    cout << endl;
    return 0;
}

// 运行结果：1 2 3 4 5

答案：1 2 3 4 5。

思路：打印语句写在递归调用之后，所以会先一层层往下（f(5)→f(4)→…→f(0)），到 n = 0 返回后开始回溯，沿路把 1、2、3、4、5 依次打印出来，于是得到正序。

考点：打印语句与递归调用的先后顺序，决定输出是正序还是倒序（展开阶段 vs 回溯阶段）。

易错：看到 f(5) 就脱口而出「5 4 3 2 1」。请一定先看打印是在递归之前还是之后。

B2推理题

题目：下面递归函数计算的是什么？写出 f(6) 的值。

C++神秘递归

int f(int n) {
    if (n <= 2) return 1;
    return f(n - 1) + f(n - 2);
}

点击查看参考答案

答案：这个函数计算斐波那契数列，f(6) = 8。数列：f(1)=1, f(2)=1, f(3)=2, f(4)=3, f(5)=5, f(6)=8。基准情况是 n<=2 返回 1。

思路：从基准情况逐层代推：f(3)=2, f(4)=3, f(5)=5, f(6)=8，这是斐波那契数列（已用程序验证）。

易错：下标从 0 开始数，把 f(6) 算成 5 或 13。

B3编程题

题目：写一个递归函数 countDigits(n)，计算正整数 n 的位数。例如 countDigits(12345) 返回 5。

提示：基准情况是 n < 10 时返回 1；递归步骤是 1 + countDigits(n / 10)。

点击查看参考答案

C++完整参考代码

#include <iostream>
using namespace std;

int countDigits(int n) {
    if (n < 10) return 1;             // 基准情况：一位数就是 1 位
    return 1 + countDigits(n / 10);   // 递归步骤：去掉个位再数
}

int main() {
    cout << countDigits(12345) << endl;   // 5
    cout << countDigits(7) << endl;       // 1
    cout << countDigits(100) << endl;     // 3
    return 0;
}

// 运行结果：
// 5
// 1
// 3

答案：if (n < 10) return 1; return 1 + countDigits(n / 10); 完整程序见左侧代码。实测 countDigits(12345) = 5，countDigits(7) = 1，countDigits(100) = 3。

思路：n / 10 相当于把个位丢掉一次，位数就少 1。所以「n 的位数 = 1 + （n/10 的位数）」；一直丢到只剩一位数（n < 10）时就是答案 1。

考点：把「去掉一位」这个操作变成递归步骤，用整数除法缩小问题规模。

易错：基准情况写成 n == 0 会把 0 算成 1 位、把 10 算成 3 位。题目限定正整数，基准写成 n < 10 最稳。

B4写输出

题目：下面程序输出什么？

C++先打印再递归

#include <iostream>
using namespace std;
void f(int n) {
    if (n <= 0) return;
    cout << n << " ";
    f(n - 1);
}
int main() {
    f(5);
    cout << endl;
    return 0;
}

点击查看参考答案

C++完整参考代码

#include <iostream>
using namespace std;

void f(int n) {
    if (n <= 0) return;      // 基准情况
    cout << n << " ";        // 展开阶段就打印，所以是倒序
    f(n - 1);
}

int main() {
    f(5);
    cout << endl;
    return 0;
}

// 运行结果：5 4 3 2 1

答案：5 4 3 2 1。

思路：打印写在递归调用之前（展开阶段）：先打印 n = 5，再叫 f(4) 打印 4，依次往下到 f(1) 打印 1，最后 f(0) 返回。输出自然是倒序。

考点：与 B1 对照——只把打印和递归的顺序换一下，输出就从正序变成倒序。

易错：把 B1 和 B4 记混。口诀：先打印后递归 = 倒序；先递归后打印 = 正序。

C 组思维挑战（4 题）

C1挑战题

题目：写一个递归函数 hanoi(n, from, aux, to)，打印汉诺塔 n 个盘子从 from 柱移到 to 柱的所有步骤。

提示：三步策略：1) 把 n-1 个从 from 移到 aux；2) 把第 n 个从 from 移到 to；3) 把 n-1 个从 aux 移到 to。

点击查看参考答案

答案：void hanoi(int n, char from, char aux, char to) { if (n == 1) { cout << "移动盘子 1 从 " << from << " 到 " << to << endl; return; } hanoi(n-1, from, to, aux); cout << "移动盘子 " << n << " 从 " << from << " 到 " << to << endl; hanoi(n-1, aux, from, to); } 汉诺塔是递归的经典应用。n 个盘子需要 2^n - 1 步。

思路：先把上面 n-1 个盘子从 from 借 to 移到 aux，再把最大盘移到 to，最后把 n-1 个从 aux 借 from 移到 to。

易错：递归调用时 from、aux、to 三个柱子的位置写错，步骤全乱。

C2陷阱题

题目：下面递归函数有什么问题？如何修复？

C++有问题的递归

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(a, b);  // 有问题
}

点击查看参考答案

问题：递归步骤 gcd(a, b) 的参数没有变化！a 和 b 都原样传进去了，b 永远不等于 0（除非一开始就是 0），导致无限递归、栈溢出。修复：return gcd(b, a % b); 每次递归 b 严格减小，最终会到达 0。

思路：检查递归是否朝基准情况推进——这里参数原样传下去，永远到不了 b == 0，改成 return gcd(b, a % b) 即可。

易错：以为写了递归调用就正确，没验证每一层参数是否严格变小。

C3编程题

题目：写一个递归函数 isPalindrome(s, i, j)，判断字符串 s 的子串 s[i..j] 是否是回文。

提示：基准情况：i >= j 时返回 true。递归步骤：如果 s[i] == s[j]，则检查 s[i+1..j-1]。

点击查看参考答案

C++完整参考代码

#include <iostream>
#include <string>
using namespace std;

// 判断 s[i..j] 这段子串是不是回文
bool isPalindrome(const string& s, int i, int j) {
    if (i >= j) return true;                // 基准：空串或只剩一个字符，都是回文
    if (s[i] != s[j]) return false;         // 两端不同，直接判否
    return isPalindrome(s, i + 1, j - 1);   // 两端相同，往里收缩一对继续比
}

int main() {
    string s = "abcba";
    cout << isPalindrome(s, 0, (int)s.size() - 1) << endl;   // 1（是回文）
    string t = "abca";
    cout << isPalindrome(t, 0, (int)t.size() - 1) << endl;   // 0（不是回文）
    return 0;
}

// 运行结果：
// 1
// 0

答案：if (i >= j) return true; if (s[i] != s[j]) return false; return isPalindrome(s, i+1, j-1); 完整程序见左侧代码。实测 "abcba" 返回 1（是回文），"abca" 返回 0（不是）。

思路：回文的定义是「首尾相同，去掉首尾后仍是回文」。于是每层只做两件事：比首尾字符；相同就往里收一格，交给下一层。i、j 相遇或交叉就说明全比完了，返回 true。

考点：基准情况 i >= j 一次覆盖了两种情形——偶数长度时 i > j（空串），奇数长度时 i == j（单字符），两者都是回文。

易错：基准写成 i == j 会让偶数长度的串比不到底（i 会跳过 j），递归停不下来。用 >= 才安全。

C4编程题

题目：写一个递归函数 countOnes(n)，计算正整数 n 在二进制表示下有多少个 1。例如 n=13（二进制 1101）返回 3。

提示：基准情况是 n=0 返回 0；递归步骤是 (n & 1) + countOnes(n >> 1)。

点击查看参考答案

C++完整参考代码

#include <iostream>
using namespace std;

// 统计 n 的二进制表示里有多少个 1
int countOnes(int n) {
    if (n == 0) return 0;                   // 基准情况：0 里没有 1
    return (n & 1) + countOnes(n >> 1);     // 取最低位 + 右移一位继续数
}

int main() {
    cout << countOnes(13) << endl;   // 13 = 1101(2)，3 个 1
    cout << countOnes(7) << endl;    // 7  = 111(2)，3 个 1
    cout << countOnes(8) << endl;    // 8  = 1000(2)，1 个 1
    return 0;
}

// 运行结果：
// 3
// 3
// 1

答案：if (n == 0) return 0; return (n & 1) + countOnes(n >> 1); 完整程序见左侧代码。实测 countOnes(13) = 3（13 = 1101₂），countOnes(7) = 3，countOnes(8) = 1。

思路：n & 1 取出最低位（是 1 就贡献 1，是 0 就贡献 0），n >> 1 把最低位丢掉。于是「n 里 1 的个数 = 最低位 + 右移一位后 1 的个数」，一路右移到 n 变成 0 为止。

考点：位运算 &（按位与）和 >>（右移）配合递归；理解基准情况为什么是 n == 0。

易错：把 n & 1 写成 n % 2、n >> 1 写成 n / 2——对正整数结果相同，但位运算更直接地表达「看二进制」的意图。另外别忘写法：>> 是右移不是比较大小。

情景导航

俄罗斯套娃 · 一层套一层

两面镜子 · 无限反射

查字典 · 遇到不懂的词查释义

借书 · 借不到就找下一本

知识探究

展开阶段（向下）

回溯阶段（向上）

递归擅长

循环擅长

案例 1：阶乘函数 —— 递归的"Hello World"

案例 2：斐波那契数列 —— 两个基准情况的递归

案例 3：递归求和 —— 从 1 加到 n

案例 4：递归打印数组 —— 从后往前输出

案例 5：递归求幂 —— a 的 n 次方

案例 6：现场捉虫 —— 三处经典错误

实践应用

题目：看清递归的执行顺序 —— 下面程序输出什么？

题目：下面这段递归代码有错误，修复它并说明原因

题目：辗转相除法求最大公约数（GCD）—— 用递归实现

总结提升

🧠 思考与启发

学习检测

忘记写基准情况（Base Case）

递归步骤参数没有缩小

基准情况漏写或多写

递归深度过大导致栈溢出

混淆"展开"和"回溯"的执行顺序

递归 = 自己调自己

两个要素缺一不可

展开阶段向下，回溯阶段向上

参数必须朝基准方向变化

调用栈 = 一摞盘子

递归深度有限制

递归调用前后的语句顺序不同

斐波那契递归效率低

练习作业

题目：判断 —— 递归函数必须有且只有一个基准情况。

题目：下面程序输出什么？

题目：写一个递归函数 reverse(n)，将一个正整数的各位数字倒序输出。例如 reverse(123) 输出 321。

题目：递归函数必须有两个要素：______（直接返回结果，不再递归）和 ______（缩小问题后调用自己）。

题目：判断 —— 递归函数调用自己时，每一层都有自己的参数和局部变量，互不影响。

题目：下面程序输出什么？

题目：写一个递归函数 power(a, n)，计算 a 的 n 次方（a^n），其中 n 是非负整数。

题目：下面程序输出什么？

题目：下面递归函数计算的是什么？写出 f(6) 的值。

题目：写一个递归函数 countDigits(n)，计算正整数 n 的位数。例如 countDigits(12345) 返回 5。

题目：下面程序输出什么？

题目：写一个递归函数 hanoi(n, from, aux, to)，打印汉诺塔 n 个盘子从 from 柱移到 to 柱的所有步骤。

题目：下面递归函数有什么问题？如何修复？

题目：写一个递归函数 isPalindrome(s, i, j)，判断字符串 s 的子串 s[i..j] 是否是回文。

题目：写一个递归函数 countOnes(n)，计算正整数 n 在二进制表示下有多少个 1。例如 n=13（二进制 1101）返回 3。

题目：递归函数必须有两个要素：（直接返回结果，不再递归）和（缩小问题后调用自己）。