递归函数引起的堆栈溢出

2021-12-07 00:00:00 function 递归 stack-overflow c++

我是 C++ 的初学者.昨天我读了递归函数，所以我决定自己写.这是我写的:

I'm a beginner in C++. Yesterday I read about recursive functions, so I decided to write my own. Here's what I wrote:

int returnZero(int anyNumber) {
    if(anyNumber == 0)
        return 0;
    else  {
        anyNumber--;
        return returnZero(anyNumber);
    }
}

当我这样做时:int zero1 = returnZero(4793);，它会导致堆栈溢出.但是，如果我将值 4792 作为参数传递，则不会发生溢出.

When I do this: int zero1 = returnZero(4793);, it causes a stack overflow. However, if I pass the value 4792 as the argument, no overflow occurs.

对原因有什么想法吗?

推荐答案

无论何时调用函数，包括递归调用，返回地址和参数通常都会被推送到 调用堆栈.堆栈是有限的，因此如果递归太深，您最终会耗尽堆栈空间.

Whenever you call a function, including recursively, the return address and often the arguments are pushed onto the call stack. The stack is finite, so if the recursion is too deep you'll eventually run out of stack space.

令我惊讶的是，在您的机器上只需要 4793 次调用即可溢出堆栈.这是一个非常小的堆栈.相比之下，在我的计算机上运行相同的代码所需的调用次数是程序崩溃前的 100 倍.

What surprises me is that it only takes 4793 calls on your machine to overflow the stack. This is a pretty small stack. By way of comparison, running the same code on my computer requires ~100x as many calls before the program crashes.

堆栈的大小是可配置的.在 Unix 上，命令是 ulimit -s.

The size of the stack is configurable. On Unix, the command is ulimit -s.

鉴于该函数是尾递归，一些编译器可能能够通过将其关闭来优化递归调用进入跳跃.一些编译器可能会更进一步:当被要求进行最大优化时，gcc 4.7.2 将整个函数转换为:

Given that the function is tail-recursive, some compilers might be able to optimize the recursive call away by turning it into a jump. Some compilers might take your example even further: when asked for maximum optimizations, gcc 4.7.2 transforms the entire function into:

int returnZero(int anyNumber) {
  return 0;
}

这正好需要两条汇编指令:

This requires exactly two assembly instructions:

_returnZero:
        xorl    %eax, %eax
        ret

非常整洁.

相关文章