使用尾递归访问树或图结构

Question

假设我有一个以递归方式访问的结构。

伪代码：

visit(node n)
{
    if (n == visited)
         return;

    //do something
    setVisited(n);
    foreach child_node in n.getChildren(){
        visit(child_node);
    }

}

根据这个线程尾递归可以在以下情况下发生：

尾递归基本上是在以下情况下：

• 只有一个递归调用
• 该调用是函数中的最后一条语句

在上面的伪代码中，递归调用是最后一条语句，但由于调用发生在循环内，因此存在多个递归调用。我猜编译器无法检测到尾递归。

我的问题是：

无论如何重构上面的代码以使其尾递归？我正在寻找一种不会删除递归的解决方案，如果有的话（例如，我不想使用堆栈来模拟递归并将其转换为迭代函数）。

这可能吗？

如果语言是相关的，我正在使用 C++。

Answer 1

所以，实际上你总是可以将一个函数重构为尾递归......大多数使用其他语言编程的人会使用延续来有效地对其进行编码。但是，我们在这里更具体地研究 C/C++ 语言，因此我假设仅通过对函数本身进行编码来摆脱它（我的意思是不向语言添加通用的延续框架）。

假设您有一个函数的迭代版本，它应该如下所示：

void iterative() {
  while (cond)
    dosomething()
}

然后，将其转换为尾递归函数只需编写：

void tailrecursive() {
  if (!cond)
    return;

  dosomething();
  tailrecursive();
}

大多数情况下，您需要将“ state ”传递给递归调用，这会添加一些以前没有用的额外参数。在您的特定情况下，您有一个预序树遍历：

void recursive_preorder(node n) {
  if (n == visited)
    return;

  dosomething(n);
  foreach child_node in n.getChildren() {
    recursive_preorder(child_node);
  }
}

迭代等价物需要引入一个堆栈来记住资源管理器节点（因此，我们添加了推送/弹出操作）：

void iterative_preorder(node n) {
  if (n == visited)
    return;

  stack worklist = stack().push(n);
  while (!worklist.isEmpty()) {
    node n = worklist.pop()
    dosomething (n);
    foreach child_node in n.getChildren() {
        worklist.push(child_node);
    }
  }
}

现在，将这个前序树遍历的迭代版本转化为尾递归函数应该给出：

void tail_recursive_preorder_rec(stack worklist) {
  if (!worklist.isEmpty()) {
    node n = worklist.pop()
    dosomething (n);
    foreach child_node in n.getChildren() {
        worklist.push(child_node);
    }
  }
  tail_recursive_preorder_rec(worklist)
}

void tail_recursive_preorder (node n) {
  stack worklist = stack().push(n);
  tail_recursive_preorder_rec(worklist);
}

而且，它为您提供了一个尾递归函数，编译器将对其进行很好的优化。享受！

Answer 2

尾递归是模仿没有堆栈[或任何其他数据结构]的循环，即O(1)没有额外的空间。

AFAIK，目前的问题是，树/图遍历[假设每个节点中没有字段]无法以如此复杂的[时间，空间]parent完成，因此无法使用单个循环来完成，没有堆栈。因此，不可能进行尾递归重构。O(n)O(1)

编辑：问题可以在 O(1) 空间中解决，但需要 O(n^2) 时间 [这是双循环]，如这篇文章中所示。