1.在堆上模拟函数调用栈

背景: 在看算法书时候, 很多地方提到要谨防递归的栈溢出问题.

分析: 递归调用时候, 有可能出现非常深的函数调用. 对于每次的函数调用, 都需要将函数体内的局部变量保存在栈上, 如果函数体内包含大量的局部变量, 那么每次递归都会占用大量的栈空间, 非常容易导致栈溢出崩溃.

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

经过分析发现, 递归的栈溢出主要是局部变量占用太多空间而导致的. 那么我们只要想办法将局部变量封装起来放在堆上, 那么就能减少栈上空间的占用, 从而防止栈溢出.

青蛙跳台阶问题的递归算法如下所示(Swift).

// 定义一个对象, 用来存储局部变量信息
class FakeStack {
    var num: Int
    init(num: Int) {
        self.num = num
    }
    
    func nextStep() -> Int {
        if num == 1 {
            return 1
        }
        
        if num == 2 {
            return 2
        }
        
        return FakeStack(num: num - 1).nextStep() + FakeStack(num: num - 2).nextStep()
    }
}

//栈上的函数调用
let stepNumber = FakeStack(num: 10).nextStep()
print(stepNumber)

如有任何错误, 请不吝赐教.

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄