用于反转链表的非迭代等价物

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 使用调用堆栈来存储指向列表中所有节点的指针,以便在调用堆栈展开时以相反的顺序访问它们.

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

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