如何将递归函数转换为使用堆栈？

Question

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

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

现在,在许多语言中,递归的最大深度,例如,如果递归深度超过某个限制,则过程将因堆栈溢出而崩溃.

如何在没有递归的情况下实现此函数,而是使用堆栈？在许多情况下,有很多局部变量 ; 它们可以存放在哪里？

Answer 1

你改变它来使用这样的堆栈:

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

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

至于你的第二个问题:

在许多情况下,有很多局部变量; 它们可以存放在哪里？

这些确实可以保存在原来的相同位置.如果变量是"doSomethingWith"方法的局部变量,只需将它们移动到那个变量中,然后将其重构为一个单独的方法.该方法不需要处理遍历,只需要处理,并且可以通过这种方式使用它自己的局部变量,仅在其范围内工作.

Answer 2

Eric Lippert 已经创建了许多关于这个主题的帖子。例如，看看这个： 递归，第二部分：使用显式堆栈展开递归函数