注册 登录
编程论坛 数据结构与算法

递归占用的栈内存有多大

lion7beckham 发布于 2013-04-10 11:17, 1049 次点击
C语言中,递归时使用栈内存。由于栈维护了每个函数调用的信息直到函数返回后才释放,这需要占用相当大的空间,尤其是程序中使用了许多递归调用的情况下。除此之外,因为有大量信息需要保存和恢复,因此生成和销毁栈帧需要耗费一定的时间。
“相当大的空间”,大约在什么数量级?我一直没有具体的概念。以下C代码中
程序代码:

/* 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);
}
,大家可以帮我评估下吗?非常感谢!
假定分别执行fact(1000)和fact(10000)。
7 回复
#2
lion7beckham2013-04-11 06:44
怎么没人理我啊。。
#3
梦想的飞跃2013-04-11 23:56
#include "fact.h"  有这种类型吗?
#4
lion7beckham2013-04-12 12:50
回复 3楼 梦想的飞跃
嗯?没把头文件发上来。你懂的~
#5
mskeheng2013-04-13 23:58
顶一下
#6
yuccn2013-04-15 12:21
你这个函数大概可以这样估算一下:
越等价于你到这个函数所用到堆栈空间,乘以递归次数

这个函数到堆栈空间在debug版本下就是一些调试信息需要到空间加上局部变量需要到空间咯

release版本下。只是函数内局部变量到空间咯

#7
nuistkevin2013-04-15 12:34
猎头职位-软件工程师
岗位职责
1.与世界顶尖的软件工程师共同开发虚拟化云计算产品
2.能独立处理和解决所负责的任务;
3.进行程序单元、功能的测试,查出软件存在的缺陷并保证其质量。
任职资格
1、 211或985高校计算机科学与技术或软件专业,英文流利;
2、 具有很强的学习能力和解决问题的能力;
3、 至少3年以上软件开发经验,精通C语言/C++,热衷于技术专研;
4、 熟练的数据结构知识体系与较强的算法能力,对堆栈、2X树、多X树有一定了解
5、 熟悉Windows, Linux X86/64 操作系统;
6、 熟悉Network configurations and environments;

工作地点:上海
有意者可以发送您的中英文简历至邮箱:
junpingwu@
QQ:2571168815
#8
Susake2013-04-15 12:46
一般系统需要在运行被调用算法之前要完成3件事
1.将参数传给被调用算法
2.为调用算法分配存储区
3.将控制转移到被调用算法的入口

返回到调用算法时,也要完成3件事
1.保存计算结果
2.释放分配的数据区
3.依照被调用的算法保存的返回地址将控制转移到调用算法
1