3

我有以下递归方法。我得到一个错误堆栈溢出。它停在-9352。我的问题,堆栈溢出是否与无限循环相同?因为这将继续调用自己。

但是,如果我使用 while、until、do 等进行无限循环,它不会给我同样的堆栈溢出错误。它一直持续到我的系统内存不足。

这是使用 Ruby

def recursion(n)
    print n
    recursion(n-1)
end

recursion(3)

输出:

3
2
1
0
.
.
.
-9352  stack overflow stops
4

1 回答 1

-1

递归和循环是可以以不同方式解决类似问题的技术(如评论中所述,它们是图灵等效的,但这不是我的领域)。

每个函数调用都会向调用堆栈添加一个框架。这需要额外的内存,并且随着您的调用链越来越深,它需要更多内存,直到超过某个限制,这会使您的堆栈overflow和程序崩溃。

您的递归代码将越来越多的帧添加到调用堆栈中,并且给定有限的内存量,将导致它溢出。您需要一些方法来告诉递归何时停止,并在内存耗尽之前这样做。这样的条件等价于base case数学归纳法中的 ,所以通常这样称呼。

注释中指出的另一个选项是使用Tail 调用优化,它替换堆栈中的当前帧,因此可以防止堆栈溢出。

您的迭代解决方案只需要固定数量的内存。

仅更改计数器或其他预定义变量的,因此不会产生任何内存开销。

如果你不限制输出,理论上它可以无限期地继续下去,但其他一些耗尽或错误很可能会杀死它。但是,这不会是循环本身中使用的变量所消耗的内存。

于 2013-09-01T00:04:51.747 回答