递归函数详解：自己调用自己

> 不同函数之间可以调来调去，递归函数却是自己调用自己

什么是递归函数

简单定义

递归嘛，多简单的事拿去！

通过前面的学习，我们知道：

• 函数可以看成一台机器，你想使用的时候直接使用就可以了
• 一个函数可以调用另一个函数
• 就相当于一台机器工作中需要另一台机器的功能，把它拿过来使用而已

函数的比喻

当然，一个函数我们也可以看作是一个人：

• 他要做一个特定的事情
• 需要帮忙时，他就叫他的一个小弟过来
• 我们就可以把这个函数看作是大哥
• 被调用的函数就是小弟

洗衣服的比喻

问题场景

假如我们模拟一个洗衣服的过程：

有一件脏衣服给一个人洗：

1. 他洗了一遍，发现只洗掉了一点污渍
2. 他就不洗了，叫上他的一个小弟来帮忙洗
3. 他就在一边等着

这个小弟：

1. 也洗了一遍，也是洗掉了一点污渍
2. 他也不洗了，再叫上他的一个小弟来洗
3. 他也在等着

后面呢就发生了循环叫小弟的过程...

终于完成

终于有一个小弟把这件衣服完全洗干净了：

• 于是他报告交给他衣服的大哥："大哥，我洗好了！"
• 然后这位大哥又向上报告："大哥，我洗好了！"
• "大哥，我洗好了！"
• "大哥，我洗好了！"

如此重复之后：

• 最初的大大大大大哥
• 接过了层层任务外包之后
• 洗干净的衣服

代码实现

问题分析

我们用代码模拟这个过程：

假如一件衣服上有100个污渍：

• 一次只能洗掉一点
• 我们需要写100个函数吗？
• 100个小弟吗？

学生： "哦，我明白了，面对考核代码行数的公司，我又多了一个应对之策了。"

老师： "那当然不是了！"

递归的妙处

函数除了调用别的函数以外，也是可以调用自己的！

学生： "啥？自己当自己的小弟吗？Cosplay角色扮演吗？"

老师： "笑儿！"

递归实现

#include <iostream>void WashClothes(int dirtyLevel) {    std::cout << "当前污渍：" << dirtyLevel << std::endl;    // 终止条件：洗干净了    if (dirtyLevel == 0) {        std::cout << "洗干净了！" << std::endl;        return;    }    // 洗掉一点污渍    std::cout << "洗掉一点污渍..." << std::endl;    // 递归调用：叫小弟来洗    WashClothes(dirtyLevel - 1);    // 小弟洗完了，向上报告    std::cout << "大哥，我洗好了！（污渍剩余：" << dirtyLevel << "）" << std::endl;}int main() {    std::cout << "开始洗衣服！" << std::endl;    WashClothes(5);    std::cout << "全部完成！" << std::endl;    return 0;}

输出：

开始洗衣服！当前污渍：5洗掉一点污渍...当前污渍：4洗掉一点污渍...当前污渍：3洗掉一点污渍...当前污渍：2洗掉一点污渍...当前污渍：1洗掉一点污渍...当前污渍：0洗干净了！大哥，我洗好了！（污渍剩余：1）大哥，我洗好了！（污渍剩余：2）大哥，我洗好了！（污渍剩余：3）大哥，我洗好了！（污渍剩余：4）大哥，我洗好了！（污渍剩余：5）全部完成！

递归的执行过程

分身术

所以我们看到这样的代码，当开始执行后：

第一个（大哥）：

1. 进入到函数内部之后，洗了一遍
2. 发现还有99个污渍，需要继续洗
3. 他就开始不干了
4. 这时候你就可以认为他使用了分身术
5. 弄一个分身来当自己的小弟

小弟洗的时候：

1. 还有99个污渍
2. 接着小弟洗了一遍，还剩下98个污渍
3. 又召唤分身当小弟
4. 不断的循环

最后一个小弟：

• 会洗完就会层层报告大哥

递归过程图解

WashClothes(5)  │  ├─ 洗一次，还剩4  │  └─ WashClothes(4)       │       ├─ 洗一次，还剩3       │       └─ WashClothes(3)            │            ├─ 洗一次，还剩2            │            └─ WashClothes(2)                 │                 ├─ 洗一次，还剩1                 │                 └─ WashClothes(1)                      │                      ├─ 洗一次，还剩0                      │                      └─ WashClothes(0)                           │                           └─ 洗干净了！返回

递归函数的定义

正式定义

像这样子在函数体内调用自己本身的函数，我们叫做递归函数。

学生： "所以我每天努力的学习，觉得还不够努力，又让自己再努力点，我算是个递归人吗？"

递归的要点

⚠️ 必须有终止条件

当大家学会递归函数之后，一定要慎重使用！

递归一定要有终止条件：

• 比如这里把污渍洗完就结束了
• 如果没有终止条件，是不是会无限循环呢？

不好意思，其实不会：

• 会直接栈溢出
• 导致程序崩溃

所以爱使用递归函数的，比较有可能是水货程序员。

あの？

无终止条件的递归

void InfiniteRecursion() {    std::cout << "调用中..." << std::endl;    InfiniteRecursion();  // ❌ 没有终止条件，会栈溢出！}

结果：

调用中...调用中...调用中......（很多次）Stack overflow! (栈溢出)程序崩溃

递归的风险

⚠️ 有终止条件就够了吗？

学生： "那我有终止条件，是不是就一定可以了呢？"

老师： "当然也不会！"

栈内存限制

一般情况下，我们不会使用递归函数，因为：

在运行过程中：

• 递归函数不断召唤小弟
• 就会消耗栈内存
• 但栈内存是比较小的
• 在Windows上只有1MB左右

假如你的衣服有100万个污渍：

• 召唤巨量的小弟
• 不就爆炸了吗？

老师： "衣服穿那么脏，你也是个人才。"

栈溢出示例

#include <iostream>void DeepRecursion(int count) {    std::cout << "第 " << count << " 次调用" << std::endl;    DeepRecursion(count + 1);  // 一直递归下去}int main() {    DeepRecursion(1);  // ❌ 会导致栈溢出    return 0;}

输出：

第 1 次调用第 2 次调用第 3 次调用...第 10000 次调用第 10001 次调用Stack overflow! (栈溢出)

经典递归案例

案例1：阶乘

阶乘的定义：

• n! = n × (n-1) × (n-2) × ... × 2 × 1
• 5! = 5 × 4 × 3 × 2 × 1 = 120

递归思路：

• n! = n × (n-1)!
• 5! = 5 × 4!
• 4! = 4 × 3!
• ...
• 1! = 1（终止条件）

#include <iostream>int Factorial(int n) {    // 终止条件    if (n == 0 || n == 1) {        return 1;    }    // 递归调用    return n * Factorial(n - 1);}int main() {    std::cout << "5! = " << Factorial(5) << std::endl;  // 120    std::cout << "10! = " << Factorial(10) << std::endl;  // 3628800    return 0;}

案例2：斐波那契数列

斐波那契数列：

• 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
• 每个数是前两个数的和

递归思路：

• Fib(n) = Fib(n-1) + Fib(n-2)
• Fib(1) = 1
• Fib(2) = 1

#include <iostream>int Fibonacci(int n) {    // 终止条件    if (n == 1 || n == 2) {        return 1;    }    // 递归调用    return Fibonacci(n - 1) + Fibonacci(n - 2);}int main() {    std::cout << "斐波那契数列前10项：" << std::endl;    for (int i = 1; i <= 10; i++) {        std::cout << Fibonacci(i) << " ";    }    std::cout << std::endl;    return 0;}

输出：

斐波那契数列前10项：1 1 2 3 5 8 13 21 34 55

案例3：汉诺塔

汉诺塔问题：

• 有三根柱子：A、B、C
• A柱上有n个盘子，大小不一
• 目标：把所有盘子从A移到C
• 规则：每次只能移动一个盘子，大盘不能在小盘上面

#include <iostream>void Hanoi(int n, char from, char to, char temp) {    if (n == 1) {        // 只有一个盘子，直接移动        std::cout << "移动盘子 1 从 " << from << " 到 " << to << std::endl;        return;    }    // 1. 把n-1个盘子从from移到temp（借助to）    Hanoi(n - 1, from, temp, to);    // 2. 把第n个盘子从from移到to    std::cout << "移动盘子 " << n << " 从 " << from << " 到 " << to << std::endl;    // 3. 把n-1个盘子从temp移到to（借助from）    Hanoi(n - 1, temp, to, from);}int main() {    int n = 3;    std::cout << "汉诺塔移动步骤（" << n << "个盘子）：" << std::endl;    Hanoi(n, 'A', 'C', 'B');    return 0;}

输出：

汉诺塔移动步骤（3个盘子）：移动盘子 1 从 A 到 C移动盘子 2 从 A 到 B移动盘子 1 从 C 到 B移动盘子 3 从 A 到 C移动盘子 1 从 B 到 A移动盘子 2 从 B 到 C移动盘子 1 从 A 到 C

递归 vs 循环

对比

阶乘的循环实现

int FactorialLoop(int n) {    int result = 1;    for (int i = 1; i <= n; i++) {        result *= i;    }    return result;}

对比：

• 递归：简洁，但有栈开销
• 循环：稍长，但性能更好

何时使用递归

✅ 适合用递归的场景

1. 问题本身具有递归性质

• 树的遍历
• 图的遍历
• 分治算法
• 回溯算法

2. 用递归更简洁

• 汉诺塔
• 快速排序
• 归并排序

3. 深度不会太深

• 避免栈溢出
• 一般不超过几千层

❌ 不适合用递归的场景

1. 深度过深

• 会导致栈溢出
• 如计算100万的阶乘

2. 重复计算多

• 如斐波那契数列
• 建议用动态规划优化

3. 循环更简单

• 简单的累加、遍历
• 用循环即可

递归优化

尾递归

尾递归：

• 递归调用是函数的最后一个操作
• 编译器可以优化成循环

// 普通递归int FactorialNormal(int n) {    if (n <= 1) return 1;    return n * FactorialNormal(n - 1);  // 递归后还要做乘法}// 尾递归int FactorialTail(int n, int acc = 1) {    if (n <= 1) return acc;    return FactorialTail(n - 1, n * acc);  // 递归是最后操作}

记忆化递归

斐波那契的优化：

#include <iostream>#include <unordered_map>std::unordered_map<int, int=""> memo;int FibonacciMemo(int n) {    // 查找缓存    if (memo.find(n) != memo.end()) {        return memo[n];    }    // 终止条件    if (n == 1 || n == 2) {        return 1;    }    // 计算并缓存    int result = FibonacciMemo(n - 1) + FibonacciMemo(n - 2);    memo[n] = result;    return result;}int main() {    std::cout << "Fib(40) = " << FibonacciMemo(40) << std::endl;    return 0;}

优化效果：

• 普通递归：超级慢
• 记忆化递归：很快

本文要点回顾

• ✨ 递归函数：函数调用自己
• ✨ 终止条件：必须有，否则栈溢出
• ✨ 栈内存：有限的，深度不能太深
• ✨ 经典案例：阶乘、斐波那契、汉诺塔
• ✨ 使用场景：树、图、分治、回溯
• ✨ 优化方法：尾递归、记忆化

记忆口诀

> 递归就是自己调自己，分身术里藏玄机。
>
> 终止条件不能忘，栈内存满程序亡。
>
> 树图分治用递归，简单循环别乱递。
>
> 尾递记忆来优化，性能提升杠杠滴。

实战练习

练习1：求和

用递归计算1+2+3+...+n

点击查看答案

int Sum(int n) {    if (n == 1) {        return 1;    }    return n + Sum(n - 1);}int main() {    std::cout << "1+2+...+100 = " << Sum(100) << std::endl;  // 5050    return 0;}

练习2：倒序打印

用递归倒序打印数字

点击查看答案

void PrintReverse(int n) {    if (n == 0) {        return;    }    std::cout << n << " ";    PrintReverse(n - 1);}int main() {    PrintReverse(10);  // 输出：10 9 8 7 6 5 4 3 2 1    return 0;}

练习3：二分查找

用递归实现二分查找

点击查看答案

int BinarySearch(int arr[], int left, int right, int target) {    if (left > right) {        return -1;  // 未找到    }    int mid = (left + right) / 2;    if (arr[mid] == target) {        return mid;  // 找到了    } else if (arr[mid] > target) {        return BinarySearch(arr, left, mid - 1, target);  // 左半部分    } else {        return BinarySearch(arr, mid + 1, right, target);  // 右半部分    }}int main() {    int arr[] = {1, 3, 5, 7, 9, 11, 13, 15};    int n = sizeof(arr) / sizeof(arr[0]);    int index = BinarySearch(arr, 0, n - 1, 7);    std::cout << "找到位置：" << index << std::endl;  // 3    return 0;}

互动时间

思考题：

1. 递归和循环有什么区别？
2. 什么情况下适合用递归？
3. 如何避免栈溢出？

如果本文对你有帮助，欢迎：

• 点赞支持
• 关注不迷路
• 评论区分享你的递归经验
• ⭐ 收藏慢慢看

---本文为"C++ 大白话"系列第 33 篇

常见问题

Q1：递归一定比循环慢吗？

A：

• 一般情况下，是的
• 递归有函数调用开销
• 但某些情况下差异不大
• 关键看具体场景和优化

Q2：如何判断递归深度？

A：

• 看终止条件
• 估算最坏情况
• 如果深度超过几千，需谨慎
• 考虑用循环或迭代

Q3：所有递归都能改成循环吗？

A：

• 理论上可以
• 但有些改起来很复杂
• 如多分支递归（树遍历）
• 建议根据场景选择

Q4：尾递归一定会被优化吗？

A：

• 不一定
• 取决于编译器
• C++标准不保证
• 但大多数编译器支持

深入理解

递归的本质

递归的三要素：

1. 递归公式

f(n) = n * f(n-1)  // 阶乘的递归公式

2. 终止条件

if (n == 0) return 1;  // 基础情况

3. 逐步逼近

每次递归都向终止条件靠近

栈帧分析

每次函数调用都会创建栈帧：

栈帧内容：- 参数- 局部变量- 返回地址- ...

递归时栈的变化：

Factorial(3)  栈帧1: n=3, 返回地址  │  └─ Factorial(2)       栈帧2: n=2, 返回地址       │       └─ Factorial(1)            栈帧3: n=1, 返回地址            │            └─ return 1                 ↓            栈帧3销毁                 ↓       栈帧2计算 2*1=2                 ↓       栈帧2销毁                 ↓  栈帧1计算 3*2=6                 ↓  栈帧1销毁

总结

递归函数的要点：

1. 定义

• 函数调用自己
• 分治思想
• 自顶向下

2. 优点

• 代码简洁
• 符合数学定义
• 易于理解

3. 缺点

• 栈开销大
• 可能栈溢出
• 性能较低

4. 使用建议

• 有终止条件
• 深度不要太深
• 适合递归的场景才用

你已经掌握了递归函数！

递归不难，关键是理解分身术的精髓！

递归函数：自己调用自己，层层分解问题！ ✨
</int,>