【C语言】递归的内存占用过程

递归

递归是函数调用自身的一种编程技术。在C语言中，递归的实现会占用内存栈（Call Stack），每次递归调用都会在栈上分配一个新的 “栈帧（Stack Frame）”，用于存储本次调用的函数局部变量、返回地址、参数等信息。简单点说：自己调自己。

顾名思义：

例子： fun(void){//一定要有结束条件 fun()}例子： 从 1 + 2 + 3 + ... + 100 

函数递归的缺陷： 非常耗内存 不建议在函数中使用递归，如果将栈的内存耗尽，程序执行会出现报错：Segmetation fault (core dumped)

那么，在递归的过程中到底发生了什么事情呢？ 以下将通过文字解析和图示说明递归对内存的占用情况，让大家直观的看见递归的过程。

栈帧（Stack Frame）的组成

每次函数调用（包括递归调用），都会在内存栈区中分配一个栈帧，主要用于存储以下内容：

1. 函数参数：函数调用时传入的参数。
2. 返回地址：函数执行完后需要返回到调用函数的位置，返回地址存储在栈帧中。
3. 局部变量：函数内部定义的局部变量。
4. 其他信息：如寄存器保存、栈指针、帧指针等（具体取决于编译器和硬件架构）。

递归调用时，每次调用都会创建一个新的栈帧，压入到内存栈中。递归结束时，函数逐层返回，栈帧依次弹出释放。

递归的内存占用过程

代码一：（上述示例）
使用递归的方式从 1 + 2 + 3 + … + 100 ：



下面举一个更复杂的例子。
代码二：

#include <stdio.h>void recursiveFunction(int n) {if (n == 0) {printf("Recursion ends.\n");return;}printf("Entering recursion: n = %d\n", n);// 递归调用recursiveFunction(n - 1);printf("Exiting recursion: n = %d\n", n);
}int main() {recursiveFunction(3);return 0;
}

执行过程分析：

1. 初次调用 recursiveFunction(3)，程序会在栈中分配一个栈帧，用于存储 n = 3 的值。
2. 函数内部调用 recursiveFunction(2)，再次分配栈帧，存储 n = 2。
3. 如此递归，直到 n = 0，递归结束，开始逐层返回，栈帧依次弹出。

图示解析（递归占用内存的变化）

假设每个栈帧包含以下内容：

• 函数参数 n。
• 函数的返回地址。
• 函数内部的局部变量（假设没有其他局部变量）。

调用栈变化过程

1. 初始状态（main 函数调用 recursiveFunction(3)）：

|--------------------|
|  main() Frame      |  <-- 栈顶
|--------------------|

2. 第一次递归调用（recursiveFunction(3)）：

|--------------------|
|  recursiveFunction |
|  参数: n = 3       |
|  返回地址: main()  |
|--------------------|
|  main() Frame      |
|--------------------|

3. 第二次递归调用（recursiveFunction(2)）：

|--------------------|
|  recursiveFunction |
|  参数: n = 2       |
|  返回地址: recursiveFunction(3) |
|--------------------|
|  recursiveFunction |
|  参数: n = 3       |
|  返回地址: main()  |
|--------------------|
|  main() Frame      |
|--------------------|

4. 第三次递归调用（recursiveFunction(1)）：

|--------------------|
|  recursiveFunction |
|  参数: n = 1       |
|  返回地址: recursiveFunction(2) |
|--------------------|
|  recursiveFunction |
|  参数: n = 2       |
|  返回地址: recursiveFunction(3) |
|--------------------|
|  recursiveFunction |
|  参数: n = 3       |
|  返回地址: main()  |
|--------------------|
|  main() Frame      |
|--------------------|

5. 第四次递归调用（recursiveFunction(0)）：

|--------------------|
|  recursiveFunction |
|  参数: n = 0       |
|  返回地址: recursiveFunction(1) |
|--------------------|
|  recursiveFunction |
|  参数: n = 1       |
|  返回地址: recursiveFunction(2) |
|--------------------|
|  recursiveFunction |
|  参数: n = 2       |
|  返回地址: recursiveFunction(3) |
|--------------------|
|  recursiveFunction |
|  参数: n = 3       |
|  返回地址: main()  |
|--------------------|
|  main() Frame      |
|--------------------|

6. 递归返回（n = 0 开始返回）：

• 栈帧逐层弹出，释放内存，最终只剩下 main() 的栈帧。

递归的内存占用与栈深度

递归深度与内存占用的关系

• 每次递归调用会分配一个新的栈帧，因此递归深度越大，占用的栈内存越多。
• 如果递归深度过大，可能导致栈溢出（Stack Overflow）。

栈溢出代码：

#include <stdio.h>void recursiveFunction(int n) {printf("n = %d\n", n);recursiveFunction(n + 1);  // 无限递归
}int main() {recursiveFunction(1);return 0;
}

运行上述程序会导致栈溢出，因为递归调用的栈帧无限增长，超过了栈的容量。

ulimit -a // 自行查看 stack size 栈的内存空间大小，开发过程中注意栈的使用量

优化递归的内存占用

1. 尾递归优化

• 尾递归是指递归调用发生在函数的最后一步，编译器可以优化为循环，避免创建多个栈帧。
  代码：

#include <stdio.h>void tailRecursiveFunction(int n, int result) {if (n == 0) {printf("Result: %d\n", result);return;}tailRecursiveFunction(n - 1, result + n);
}int main() {tailRecursiveFunction(5, 0);  // 计算 1+2+3+4+5return 0;
}

• 尾递归可以被优化为循环，避免栈溢出。

2. 转换为迭代

• 如果递归深度过大，可以将递归转换为迭代，用循环替代递归。
  代码：

#include <stdio.h>void iterativeFunction(int n) {while (n > 0) {printf("n = %d\n", n);n--;}
}int main() {iterativeFunction(5);return 0;
}

综上。便是递归的内存占用过程。递归虽然简单优雅，但需要仔细处理内存占用和递归深度问题，特别是在资源受限的嵌入式系统中需要特别注意内存空间的使用情况。

• 内存占用的特点：
  • 每次递归调用占用一个栈帧，存储函数参数、返回地址、局部变量等。
  • 栈帧数量与递归深度成正比。
• 图示说明：
  • 栈的内存布局是递归调用的直观体现，栈帧逐层压入和弹出的过程展示了递归的内存管理。
• 优化建议：
  • 使用尾递归或将递归转换为迭代以避免栈溢出。
  • 控制递归深度，避免过深的递归调用。

以上。仅供学习与分享交流，请勿用于商业用途！转载需提前说明。

我是一个十分热爱技术的程序员，希望这篇文章能够对您有帮助，也希望认识更多热爱程序开发的小伙伴。
感谢！