如何转换一个递归函数使用堆栈？ [英] How to convert a recursive function to use a stack?

问题描述

假设我有一棵树用深度优先搜索遍历，而我的算法遍历它看起来是这样的：

Suppose that I have a tree to traverse using a Depth First Search, and that my algorithm for traversing it looks something like this:

algorithm search(NODE):
  doSomethingWith(NODE)
  for each node CHILD connected to NODE:
    search(CHILD)

现在在许多语言有一个最大深度递归，例如，如果递归的深度为超过一定限度，则过程会崩溃一个堆栈溢出。

Now in many languages there is a maximum depth to recursion, for example if the depth of recursion is over a certain limit, then the procedure will crash with a stack overflow.

如何此功能，而不递归来实现，并与而非栈？在许多情况下，有很多局部变量;在那里他们可以存储？

How can this function be implemented without the recursion, and instead with a stack? In many cases, there are a lot of local variables; where can they be stored?

推荐答案

您更改为使用栈像这样：

You change this to use a stack like so:

algorithm search(NODE):
  createStack()
  addNodeToStack(NODE)

  while(stackHasElements)
      NODE = popNodeFromStack()
      doSomethingWith(NODE)
      for each node CHILD connected to NODE:
         addNodeToStack(CHILD)

关于你的第二个问题：

As for your second question:

在许多情况下，有很多的局部变量;在那里他们可以存储？

In many cases, there are a lot of local variables; where can they be stored?

这些真的可以保持在相同的位置，因为他们原本。如果变量是本地的doSomethingWith的方法，只是将它们移动到这一点，重构了到一个单独的方法。该方法不需要处理遍历，仅该处理，并且可以有其自己的局部变量这种方式工作在它的范围仅

These really can be kept in the same location as they were originally. If the variables are local to the "doSomethingWith" method, just move them into that, and refactor that into a separate method. The method doesn't need to handle the traversal, only the processing, and can have it's own local variables this way that work in its scope only.

这篇关于如何转换一个递归函数使用堆栈？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！