当前位置:网站首页>我的递归从不爆栈
我的递归从不爆栈
2022-08-02 17:42:00 【高级摸鱼工程师】
聊算法的时候,「递归」是避不开的一种技巧,因为很多算法其实会借助此技巧去实现。
那么问题来了,用不好递归会「爆栈」️️️ StackOverFlow
but ! 「尾递归」不会爆栈!
那么尾递归相比正常递归有什么特点呢?
- 尾调用函数本身,没有多余计算逻辑。
- 优化栈空间,从O(n)到O(1)
以 Python 为例,主要区分普通递归和尾递归对栈空间的使用:
def recsum(x):
if x == 1:
return x
else:
return x + recsum(x - 1)
调用recsum(5)为例,相应的栈空间变化如下:
recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1)))
5 + (4 + (3 + 3))
5 + (4 + 6)
5 + 10
15
可观察,堆栈从左到右,增加到一个峰值后再计算从右到左缩小,这往往是我们不希望的。修改以上代码,可以成为尾递归:
def tailrecsum(x, running_total=0):
if x == 0:
return running_total
else:
return tailrecsum(x - 1, running_total + x)
对比后者尾递归对内存的消耗:
tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15
ps : tailrecsum(4, 5) 执行的时候,tailrecsum(5, 0) 在栈上其实就可以回收掉了。
可以看到尾递归相比普通递归,栈空间做到了O(1)的复杂度,也就起到了内存优化的作用。
那么因为是O(1)复杂度,就肯定不会爆栈了。
引用
边栏推荐
猜你喜欢
随机推荐
golang刷leetcode 经典(2)拓扑排序
潮玩的“第二春”,在哪?
织梦自定义表单添加全选和全不选功能按钮
再获权威认证!马上消费安逸花APP通过中国信通院“金融APP人脸识别安全能力评测”
故障分析 | 一条 SELECT 语句跑崩了 MySQL ,怎么回事?
【案例】2D变换-旋转动画
暴跌99.7%后,谁还在买卖「二舅币」?
golang学习之七:并发编程基础(goroutine、channel、select)
恒驰5真的没大卖
谁抢走了华大基因的生意?
字节面试官狂问我:你没有高并发、性能调优经验,为什么录取你?
今年上半年,我国公路建设总体形势持续向好
多聚体/壳聚糖修饰白蛋白纳米球/mPEG-HSA聚乙二醇人血清白蛋白纳米球的制备与研究
2022最新版SSM源码分析:一套教程助你深入理解底层原理,提高核心竞争力!
红队实战靶场ATT&CK(一)
租房小程序自动定位城市
CUDA+Pycharm-gpu版本+Anaconda安装
9月起中国给予多哥等16国98%税目产品零关税待遇
牛津硕士进碳圈,高瓴红杉经纬一起投了
Arduino hardware programming introduction to language learning