递归中 栈溢出问题

3,839 阅读2分钟

一、递归中为什么会有栈溢出

在一次方法调用中,内部的临时变量和方法调用栈帧是放到栈空间中,普通的递归是需要记录所有的调用栈,才能计算出正确的结果。

比如一个n的叠加逻辑,不考虑数学公式直接用递归的方式:

- (NSUInteger)caluSum:(NSUInteger)num {
    if (num == 0) {
        return 0;
    }
    
    return num + [self caluSum:num-1];
}

调用栈如下:

如果递归深度非常深,那么就可能会栈溢出,通常会报错:Thread 1: EXC_BAD_ACCESS 俗称:Stack Overflow

二、栈溢出怎么处理

一般来说遇到这类问题都是使用循环来替换递归的方式,但是从思考方式上来说,我更喜欢递归的思维方式更符合人类思考的方式。

内部如果产生大量临时变量,造成内存爆掉。通常使用@autoreleasepool让临时变量提前释放。

  1. 使用循环来替换 循环中的临时变量不会像普通递归一样一直保存直到所有方法调用栈全部展开,所以栈的深度不会一直增加也就不会有栈溢出的情况。
- (NSUInteger)culuSumWhileMothod:(NSUInteger)num {
    NSUInteger total = 0;
    for (int i = 0; i <= num; i++) {
        total += i;
    }
    
    return total;
}
  1. 使用尾递归 尾递归就是让函数里的最后一个动作是一个函数调用的形式,这个调用的返回值将直接被当前函数返回,从而避免在栈上保存状态。每次递归时都会重用stack,这样一来能够提升性能,这需要语言或编译器的支持,如果没有编译器支持哪怕没有临时变量,但是方法的调用栈一样会在栈中保存。在Objective-c 和 swift在 release 运行环境下是支持尾递归优化的。

尾递归写法如下:

- (NSUInteger)sumInternal:(NSUInteger)n current:(NSUInteger)current {
    if (n == 0) {
        return current;
    } else {
        return [self sumInternal:n-1 current:current+n];
    }
}

尾调用 - 维基百科,自由的百科全书
Swifter - 尾递归