C++递归零基础完整教程

面向GESP5级，零基础友好，所有代码附带详细注释，通俗易懂，包含概念、示例、对比、完整带选项的选择判断题、课后练习题、避坑要点。

目录

1. 什么是递归
2. 生活与数学例子理解递归
3. 递归两大必备要素
4. 阶乘完整代码示例
5. 递归执行过程详解
6. 递归与递推（循环迭代）对比
7. 递归优缺点与不适合递归的场景
8. 经典判断题、选择题实战（全部带选项）
9. 课后练习题（完整选项+解析）
10. 递归常见错误与避坑
11. 考试做题技巧

---

1. 什么是递归

递归：一个函数，在它自己的函数体内调用它自身，就叫递归函数。

⚠️重要提醒：递归不能无限调用自己，必须设置停止条件，否则程序会崩溃。

2. 生活和数学例子理解递归

生活例子：拆套娃

现在有一组一层套一层的套娃，想要拿到最里面最小的娃娃：

1. 打开当前这一层娃娃（重复执行的动作）
2. 如果里面还有娃娃，继续打开
3. 如果已经是最小的娃娃，停止打开（停止条件）

两件事：

1. 重复做一件事（调用自己）
2. 什么时候停下来（停止条件）

数学例子：阶乘

$n!$ 读作n的阶乘。

$$n! = n \times (n-1)\times(n-2)\dots\times 1$$

数学规定：$\boldsymbol{0! = 1}$

我们可以把阶乘改写成分段形式：

$$\begin{cases} f(0)=1 \quad \text{遇到0直接返回1，停止计算} \\ f(n)=n \times f(n-1) \quad \text{大问题拆成更小的子问题} \end{cases} $$

3. 递归两大必备要素

写任何递归函数，两个条件缺一不可：

1. 递归边界（退出条件）：满足这个条件，直接return，不再调用自己。没有边界=无限递归，程序栈溢出崩溃。
2. 递归体：函数内部调用自身，把大问题拆解成规模更小的子问题。

口诀：有边界，有自调用，才是递归。

4. C++阶乘递归完整代码（带注释）

#include <iostream>
using namespace std;

// 求n的阶乘
int fac(int n)
{
    // ----------------递归边界：停止条件----------------
    // 数学规定0!等于1，到这里不再继续调用
    if(n == 0)
    {
        return 1;
    }
    // ----------------递归体：调用自己----------------
    // n! = n * (n‑1)!
    return n * fac(n - 1);
}

int main()
{
    // 计算5! = 5*4*3*2*1 =120
    cout << fac(5) << endl;
    return 0;
}

如果把if(n==0) return 1;删掉，函数会不停执行fac(n‑1)，无限调用，程序直接报错崩溃。

5. 递归是怎么运行的？执行流程

调用fac(5)的完整流程：

递归分为两个阶段：向下递推（一层层进入函数），向上回溯（碰到边界后一层层返回结果）

进入 fac(5)
    进入 fac(4)
        进入 fac(3)
            进入 fac(2)
                进入 fac(1)
                    进入 fac(0)  //触发边界条件 return 1
                退出 fac(1): 1 * fac(0) = 1*1 =1
            退出 fac(2): 2 * fac(1) =2*1 =2
        退出 fac(3): 3 * fac(2) =3*2 =6
    退出 fac(4): 4 * fac(3) =4*6 =24
退出 fac(5): 5 * fac(4) =5*24 =120

C++会使用系统栈保存每一层递归的参数、局部变量。每递归调用一次，栈就多存一份数据。递归深度越大，占用栈空间越多。

6. 递归 vs 递推（循环迭代）

递推就是用for/while循环解决同样的问题，从已知小结果，一步步算出大结果。

对比项目	递归	递推（循环迭代）
解题方向	自顶向下，大问题拆小问题	自底向上，从小结果推导出大结果
数据存储	系统栈自动保存每层数据	手动用变量、数组保存中间结果
代码简洁度	代码简短，逻辑清晰	代码相对更长
时间效率	存在函数调用开销，速度慢	没有函数调用，运行更快
空间效率	占用栈空间大，深度过大会栈溢出	占用内存小，不容易崩溃

阶乘循环递推版本示例：

#include <iostream>
using namespace std;

int fac_loop(int n)
{
    int res = 1;
    for(int i = 1; i <= n; i++)
    {
        res = res * i;
    }
    return res;
}

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

7. 递归优缺点 & 不适合递归的场景

✅递归优点：

1. 代码简短，很多复杂问题（汉诺塔、树操作）用递归写逻辑非常直观。

❌递归缺点：

1. 每一次函数调用都有额外开销；
2. 深度大的时候消耗大量栈内存，容易栈溢出；
3. 部分场景会产生大量重复计算。

❗不适合递归典型场景：朴素写法求斐波那契数列

fib(5)
├ fib(4)
│  ├fib(3)
│  │ ├fib(2)
│  │ └fib(1)
│  └fib(2)
└ fib(3)
   ├fib(2)
   └fib(1)

可以看到fib(3)、fib(2)被反复重复计算。这种情况优先使用循环。

8. 经典判断题、选择题实战（完整带选项）

判断题

正确选√，错误选×

1. 递归算法必须有一个明确的结束条件，否则会导致无限递归并可能引发栈溢出。（） ✅答案：√ 解析：递归边界必不可少，没有边界会无限调用函数。

2. 在C++中，递归的实现方式通常会占用更多的栈空间，递归深度过大会导致栈溢出。（） ✅答案：√ 解析：每一层递归的参数、局部变量都保存在系统栈。

3. 对于标准数学函数sin(x)，语句y=sin(sin(x));是一种递归调用。（） ✅答案：× 解析：递归要求函数内部调用自己本身，这里只是外层调用sin，sin函数内部没有调用sin。

4. 递归函数每次调用自身时，系统都会为新开启的函数分配内存，存储局部变量、调用地址，递归通常比迭代消耗更多内存。（） ✅答案：√

5. 下面这段C++代码属于递归实现斐波那契数列。（）

int Fibo(int N) {
    if (N == 1 || N == 2)
        return 1;
    else {
        int m = fiboA(N - 1);
        int n = fiboB(N - 2);
        return m + n;
    }
}

✅答案：× 解析：函数内部调用fiboA、fiboB，不是调用自身Fibo，不属于递归。

---

选择题1

#include <iostream>
using namespace std;

void fun(int n) {
    cout << n << " ";
    if (n == 1 || n == 2)
        return;
    fun(n - 2);
    fun(n - 1);
}

int main(){
    fun(4);
    return 0;
}

当调用fun(4)，屏幕输出序列为（） A. 4 3 2 1 B. 1 2 3 4 C. 4 2 3 1 2 D. 4 2 3 2 1

✅答案：C 解析：

1. fun(4)输出4，调用fun(2)
2. fun(2)输出2，触发return返回
3. fun(4)继续调用fun(3)
4. fun(3)输出3，调用fun(1)
5. fun(1)输出1触发return
6. fun(3)调用fun(2)输出2，return结束。

选择题2

#include <iostream>
using namespace std;

//循环求1~n的和
int sumA(int n) {
    int sum = 0;
    for (int i=1; i<n+1; i++)
        sum += i;
    return sum;
}

//递归求1~n的和
int sumB(int n) {
    if (n == 1)
        return 1;
    else
        return n + sumB(n-1);
}

int main() {
    int n = 0;
    cin >> n;
    cout << sumA(n) << " " << sumB(n) << endl;
    return 0;
}

有关代码说法错误的是（） A. sumA()用循环求从1到N之和，sumB()用递归方式求从1到N之和。 B. 默认情况下，如果输入正整数1000，能实现求从1 到1000 之和。 C. 默认情况下，如果输入正整数100000，能实现求从1到100000 之和。 D. 一般说来， sumA() 的效率高于sumB()。

✅答案：C 解析：sumB递归深度达到100000层，栈空间不足，栈溢出崩溃；循环sumA不受影响。

选择题3

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

string sReverse(string sIn) {
    if (sIn.length() <= 1) {
        return sIn;
    } else {
        return _______________;
    }
}

int main() {
    string sIn;
    cin >> sIn;
    cout << sReverse(sIn) << endl;
    return 0;
}

代码递归实现字符串反序，横线处应该填写（） A. sIn[sIn.length() - 1] + sReverse(sIn.substr(0, sIn.length() - 1)); B. sIn[0] + sReverse(sIn.substr(1, sIn.length() - 1)); C. sReverse(sIn.substr(0, sIn.length() - 1)) + sIn[sIn.length() - 1]; D. sReverse(sIn.substr(1, sIn.length() - 1)) + sIn[sIn.length() - 1];

✅答案：A 解析：把字符串最后一个字符放到最前面，剩下的子串继续递归反转。

9. 课后练习题（完整选项+解析）

练习1

int fun(int a, int b) {
    if (a%b == 0)
        return b;
    else
        return fun(b, a%b);
}

fun(20,12)的返回值为（） A. 20 B. 12 C. 4 D. 2

✅答案：C 解析：

1. fun(20,12)：20%12=8 → fun(12,8)
2. fun(12,8)：12%8=4 → fun(8,4)
3. fun(8,4)：8%4==0，返回4

练习2（汉诺塔）

#include <iostream>
using namespace std;

// 将N个圆盘从A通过B移动C
void Hanoi(string A, string B, string C, int N) {
    if (N == 1) {
        cout << A << "->" << C << endl;
    } else {
        Hanoi(A, C, B, N-1);
        cout << A << "->" << C << endl;
        _______________;
    }
}

int main() {
    Hanoi("甲","乙","丙",3);
    return 0;
}

横线处应填入代码是（） A. Hanoi(B, C, A, N - 2) B. Hanoi(B, A, C, N - 1) C. Hanoi(A, B, C, N - 2) D. Hanoi(C, B, A, N - 1)

✅答案：B 解析：把N‑1个圆盘，从B辅助柱借助A移动到目标C柱。

练习3

#include <iostream>
using namespace std;

int jum(int N) {
    cout << N << "#";
    if (N == 1 || N == 2) {
        return N;
    } else {
        return jum(N-1) + jum(N-2);
    }
}

int main() {
    cout << jum(4) << endl;
    return 0;
}

下面代码执行后的输出是（）。 A. 4#3#2#2#4 B. 4#3#2#2#1#5 C. 4#3#2#1#2# D. 4#3#2#1#2#5

✅答案：D 解析：先打印4#3#2#1#2#，再输出函数返回计算结果5。

练习4

#include <iostream>
using namespace std;

int stepCount = 0;

int fracA(int N) {
    stepCount += 1;
    cout << stepCount << "->";
    int rtn = 1;
    for(int i=1;i<=N;i++)
        rtn *= i;
    return rtn;
}

int fracB(int N) {
    stepCount += 1;
    cout << stepCount << "->";
    if (N == 1)
        return 1;
    return N*fracB(N - 1);
}

int main () {
    cout << fracA(5);
    cout << "<===>";
    cout << fracB(5);
    return 0;
}

执行后输出是（） A. 1->120<===>2->120 B. 1->120<===>1->120 C. 1->120<===>1->2->3->4->5->120 D. 1->120<===>2->3->4->5->6->120

✅答案：D 解析：全局变量stepCount不会自动清零。fracA调用一次，stepCount=1；fracB递归调用5次，stepCount持续累加为2、3、4、5、6。

10.递归常见错误与避坑清单

1. ❌忘记写递归边界 → 无限递归，栈溢出程序崩溃。
2. ❌递归边界条件写错，返回值错误，全部结果出错。
3. ❌函数内部调用别的函数，不是调用自己，误以为是递归。
4. ❌递归深度太大（上万层），栈溢出，此时改用循环。
5. ❌滥用全局变量，递归过程中全局变量持续累加，不会重置。
6. ❌朴素斐波那契递归，大量重复计算，运行速度极慢。

11.考试做题技巧

拿到递归题目不要靠脑子空想，拿草稿纸手写：

1. 顺着函数调用，一步步向下走到递归边界，记下边界返回值。
2. 再一层一层向上回代计算每一层返回结果。

做题口诀：先往下走到底，再回头算结果。