c++ - 反转链表的非迭代等价物

Question

我正在阅读 RobertSedwick 的算法书中的列表遍历。函数定义如下所示。有人提到，遍历和删除函数可以有迭代计数器部分，但 traverseR 不能有。我的问题是为什么 traverseR 不能有迭代对应部分？是不是如果递归调用不是函数的结束，即像遍历那样我们就不能迭代，我的理解对吗？

感谢您的宝贵时间和帮助。

void traverse(link h, void visit(link))
  { 
    if (h == 0) return;
    visit(h); 
    traverse(h->next, visit);
  }
void traverseR(link h, void visit(link))
  { 
    if (h == 0) return;
    traverseR(h->next, visit);
    visit(h); 
  }
void remove(link& x, Item v)
  { 
    while (x != 0 && x->item == v) 
      { link t = x; x = x->next; delete t; }
    if (x != 0) remove(x->next, v); 
  }

Answer 1

traverseR 使用调用堆栈来存储指向列表中所有节点的指针，以便在调用堆栈展开时可以以相反的顺序访问它们。

为了在没有调用堆栈的情况下(即非递归地)执行此操作，您需要一些其他类似堆栈的数据结构来存储这些指针。

其他函数只是在当前节点上工作并继续前进，在递归函数调用返回后不需要存储任何东西以供使用。这意味着可以用循环替换尾递归(通过修改代码，或者根据编译器的不同，让它确定这是可能的并自行进行转换)。