c++ - 使用尾递归访问树或图形结构

Question

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

伪代码:

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

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

}

根据这个thread尾递归发生在以下情况:

Tail recursion is basically when:

• there is only a single recursive call
• that call is the last statement in the function

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

我的问题是:

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

这可能吗？

如果语言相关，我会使用 C++。

Answer 1

因此，实际上您可以始终将函数重构为尾递归...大多数使用其他语言编程的人会使用延续来高效地编写代码。但是，我们在这里更具体地查看 C/C++ 语言，因此我假设只需对函数本身进行编码即可摆脱这种情况(我的意思是不向该语言添加通用延续框架)。

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

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

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

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

  dosomething();
  tailrecursive();
}

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

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

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

迭代等价物需要引入一个堆栈来记住探索者节点(因此，我们添加了 push/pop 操作):

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);
}

而且，它为您提供了一个尾递归函数，编译器可以很好地对其进行优化。享受吧!