如何将递归函数转换为使用堆栈? [英] 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)

至于你的第二个问题:

在很多情况下，有很多局部变量；它们可以存放在哪里?

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屋！