Closed. This question needs to be more focused。它当前不接受答案。












想改善这个问题吗?更新问题,使其仅通过editing this post专注于一个问题。

6年前关闭。



Improve this question





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

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

这是使用Ruby

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

recursion(3)


输出:

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

最佳答案

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

每个函数调用都会在调用堆栈中添加一个框架。这需要更多的内存,并且随着调用链的不断深入,它还需要更多的内存,直到超过特定限制,这会使您的堆栈overflow崩溃。

您的递归代码将越来越多的帧添加到调用堆栈,并且在给定有限内存量的情况下,它将导致其溢出。您需要某种方法来告知递归何时停止,并在内存耗尽之前执行此操作。这种条件与数学归纳中的base case等效,因此通常将其称为。

注释中指出的另一个选择是利用Tail call优化,该优化将替换堆栈中的当前帧,因此可以防止堆栈溢出。

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

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

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

关于loops - 了解递归与循环 ruby ,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/18503110/

10-10 18:27
查看更多