Closed. This question needs to be more focused。它当前不接受答案。
想改善这个问题吗?更新问题,使其仅通过editing this post专注于一个问题。
6年前关闭。
Improve this question
我有以下递归方法。我收到一个错误堆栈溢出。它在-9352处停止。我的问题是,堆栈溢出是否与无限循环相同?因为这会不断调用自己。
但是,如果我用while,直到,do等进行无限循环,则不会给我同样的堆栈溢出错误。它一直持续到我的系统内存不足为止。
这是使用Ruby
输出:
想改善这个问题吗?更新问题,使其仅通过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/