递归占用的栈内存有多大C语言中,递归时使用栈内存。由于栈维护了每个函数调用的信息直到函数返回后才释放,
递归占用的栈内存有多大
C语言中,递归时使用栈内存。由于栈维护了每个函数调用的信息直到函数返回后才释放,这需要占用相当大的空间,尤其是程序中使用了许多递归调用的情况下。除此之外,因为有大量信息需要保存和恢复,因此生成和销毁栈帧需要耗费一定的时间。
“相当大的空间”,大约在什么数量级?我一直没有具体的概念。以下C代码中,大家可以帮我评估下吗?非常感谢!
假定分别执行fact(1000)和fact(10000)。
/* fact.c */
#include "fact.h"
int fact(int n) {
if(n < 0)
return 0
else if (n == 0)
return 1;
else if (n == 1)
return 1;
else
return n*fact(n-1);
}
递归 内存 栈
[解决办法]对于x86架构来说,基本就是push和pop指令。函数调用的时候一般只会push函数自己会用到的寄存器。用到很多寄存器的话那就会push很多东西。
具体push了什么东西直接翻汇编就知道了。
[解决办法]好像操作系统不同,对栈的大小定义也不同。
在JAVA中定义栈大小默认是48K,最小可以设置为32K。
[解决办法]深度不可预估还是别递归了.
[解决办法]一般而言,在 X86 32位系统中,一次函数调用消耗的栈空间大约是:
4字节返回地址;
4*n字节的参数,n是参数个数;
12字节的寄存器保护区(EBP ESI EDI)
4*m字节局部变量,m 是声明在函数内部变量的个数
所以,对于楼主给出的实例,一次调用耗用的内存大小是
4+4*1+12=20字节
若递归 1000 次,大约耗 20KB 栈空间
若递归 10000 次,大约耗 200KB 栈空间
[解决办法]Q1. 若返回值是个大结构体,那必然不是4字节了吧.
A1. 是的. 所以不主张返回结构体,而是返回指针.
Q2. 尾递归可以大大提高效率
A2. 提高的幅度很有限,可以忽略.
Q3. 是否还需要考虑栈帧之间的空余内存
A3. 不需要.实际上,栈帧之间没有空余内存.
[解决办法]可以做一个无限递归,把磁盘和内存都占满的程序。
[解决办法]debug版本和release版本不一样, CPU不同也不一样.
提供几个简单的思路.
1.
在最外层和最深层也就是递归退出的地方, 打印出当前栈所处地址.
两者相减大概可以知道栈空间使用.
2.
a. 修改link工具, 让exe默认的stack比较小.
b. 创建一个线程专门做递归调用, 创建线程的时候, 给定一个reserve/commit的栈大小. 允许. 成功了, 就重复, 每次都缩小stack, 直到遇到一个stack大小. 线程栈破坏退出. 这样就可以知道精确的堆栈的需求. (当然包含了系统线程启动函数和异常帧的大小)
[解决办法]尾递归编译器容易优化成循环。