网站模板代理电话,做网站海报,淘宝网站优化实例,网站建设需要编码不递归
递归是函数调用自身的一种编程技术。在C语言中#xff0c;递归的实现会占用内存栈#xff08;Call Stack#xff09;#xff0c;每次递归调用都会在栈上分配一个新的 “栈帧#xff08;Stack Frame#xff09;”#xff0c;用于存储本次调用的函数局部变量、返回地…递归
递归是函数调用自身的一种编程技术。在C语言中递归的实现会占用内存栈Call Stack每次递归调用都会在栈上分配一个新的 “栈帧Stack Frame”用于存储本次调用的函数局部变量、返回地址、参数等信息。简单点说自己调自己。
顾名思义
例子 fun(void){//一定要有结束条件 fun()}例子 从 1 2 3 ... 100 函数递归的缺陷 非常耗内存 不建议在函数中使用递归如果将栈的内存耗尽程序执行会出现报错Segmetation fault (core dumped)那么在递归的过程中到底发生了什么事情呢 以下将通过文字解析和图示说明递归对内存的占用情况让大家直观的看见递归的过程。
栈帧Stack Frame的组成
每次函数调用包括递归调用都会在内存栈区中分配一个栈帧主要用于存储以下内容
函数参数函数调用时传入的参数。返回地址函数执行完后需要返回到调用函数的位置返回地址存储在栈帧中。局部变量函数内部定义的局部变量。其他信息如寄存器保存、栈指针、帧指针等具体取决于编译器和硬件架构。
递归调用时每次调用都会创建一个新的栈帧压入到内存栈中。递归结束时函数逐层返回栈帧依次弹出释放。
递归的内存占用过程
代码一上述示例 使用递归的方式从 1 2 3 … 100 下面举一个更复杂的例子。 代码二
#include stdio.hvoid 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;
}执行过程分析
初次调用 recursiveFunction(3)程序会在栈中分配一个栈帧用于存储 n 3 的值。函数内部调用 recursiveFunction(2)再次分配栈帧存储 n 2。如此递归直到 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.hvoid recursiveFunction(int n) {printf(n %d\n, n);recursiveFunction(n 1); // 无限递归
}int main() {recursiveFunction(1);return 0;
}运行上述程序会导致栈溢出因为递归调用的栈帧无限增长超过了栈的容量。
ulimit -a // 自行查看 stack size 栈的内存空间大小开发过程中注意栈的使用量优化递归的内存占用
1. 尾递归优化
尾递归是指递归调用发生在函数的最后一步编译器可以优化为循环避免创建多个栈帧。 代码
#include stdio.hvoid tailRecursiveFunction(int n, int result) {if (n 0) {printf(Result: %d\n, result);return;}tailRecursiveFunction(n - 1, result n);
}int main() {tailRecursiveFunction(5, 0); // 计算 12345return 0;
}尾递归可以被优化为循环避免栈溢出。
2. 转换为迭代
如果递归深度过大可以将递归转换为迭代用循环替代递归。 代码
#include stdio.hvoid iterativeFunction(int n) {while (n 0) {printf(n %d\n, n);n--;}
}int main() {iterativeFunction(5);return 0;
}综上。便是递归的内存占用过程。递归虽然简单优雅但需要仔细处理内存占用和递归深度问题特别是在资源受限的嵌入式系统中需要特别注意内存空间的使用情况。
内存占用的特点 每次递归调用占用一个栈帧存储函数参数、返回地址、局部变量等。栈帧数量与递归深度成正比。 图示说明 栈的内存布局是递归调用的直观体现栈帧逐层压入和弹出的过程展示了递归的内存管理。 优化建议 使用尾递归或将递归转换为迭代以避免栈溢出。控制递归深度避免过深的递归调用。
以上。仅供学习与分享交流请勿用于商业用途转载需提前说明。
我是一个十分热爱技术的程序员希望这篇文章能够对您有帮助也希望认识更多热爱程序开发的小伙伴。 感谢
