Chinaunix首页 | 论坛 | 博客
  • 博客访问: 31921
  • 博文数量: 41
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 80
  • 用 户 组: 普通用户
  • 注册时间: 2016-06-19 19:25
  • 认证徽章:
个人简介

迷茫的开发

文章分类

全部博文(41)

文章存档

2019年(13)

2017年(10)

2016年(18)

我的朋友

分类: C/C++

2017-11-14 19:29:49

递归在解决一些分治问题时,可能会比较好翻译成代码;而且有很多问题本身可以用递归来描述,比如:快排、二叉树的遍历等。但是递归在实际项目中可能会禁止使用(可以用额外分配栈来显示使用),它主要的问题是:
1.递归是函数自己调用自己。
而函数调用是有时间和空间的开销:每次调用要在内存栈中分配空间以保存参数、返回地址以及临时变量,而且向栈里压入数据和弹出数据都需要时间。
2.递归中函数计算可能很多都是重复的
这是从算法角度计算的开销了,这主要是递归的时候有超过1个的递归式子。
比如,像f(n) = af(n-1)+b,这个是没有额外的开销,但是像f(n)=f(n-1)+f(n-2) (斐波那契数列),在计算f(n)时,需要f(n-1)、f(n-2);在计算f(n+1)时需要f(n)、f(n-1)——这本来是上一轮已经计算完成的,但是使用递归需要重新计算。
3.可能引起栈溢出
每个线程有自己的私有空间,VS默认是1M,GCC默认是10M。
这一点完全是致命的,以决定基本上能使用递归的都应该用避免(数据量过大栈溢出会导致程序完全崩溃)
阅读(157) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册