可以用迭代代替这个递归吗？

Question

有两种类型的工人:雇员和上级。

上级有下属集合，哪些项目是员工或上级。

上级的工资取决于其各级下属的工资。

现在我用递推法计算下属的工资：

decimal SubordinatesSalary()
{
  decimal salary = 0;
  foreach ( Worker subordinate in Subordinates )
  {
    salary = salary + subordinate.SalaryPrim();
    Superior subordinateAsSuperior = subordinate as Superior;
    if ( subordinateAsSuperior != null )
      salary = salary + subordinateAsSuperior.SubordinatesSalary();
  }
  return salary;
}

可以用迭代代替这个递归吗？

Answer 1

是的是可能的。可以用迭代替换任何递归。用尾尾递归来实现这一点真的很容易。你只要把它改成循环。如果不是尾端，则需要将局部变量存储在堆栈中，并从堆栈中推和弹出(因为这都是递归函数调用提供给您的)。

虽然它最初看起来像是有尾尾递归，但是没有，因为它在一个循环中。当循环到外部循环时，您需要创建一个外部循环，并将局部变量(如worker)推送到外部循环。

Answer 2

是的，是这样的。

带走所有的人。

按“等级”(“绝对位置”)排序。最低员工优先。然后是他们的上级。然后是他们的上级。然后..。最后是最高的“总统”。正确地这样做可能会很棘手。

对员工列表进行迭代，并逐个分配薪资。当你完成第一批最低级别的员工时，你就可以找到第一级的上级，并且你可以很容易地计算出他们的工资，因为所有低级别的员工都已经完成了，并且保证他们的工资已经被处理了，并且你不需要递归地“扫描”这个人的下属来计算它。

但是..。这真的合理吗？我认为当前的递归方法非常简洁。

Answer 3

谢谢大家。以下是我的非递归解决方案：

decimal SubordinatesSalary()
{
  decimal salary = 0;
  Stack<Worker> stack = new Stack<Worker>( Subordinates );
  while ( stack.Count > 0 )
  {
    Worker subordinate = stack.Pop();
    salary = salary + subordinate.SalaryPrim();
    Superior subordinateAsSuperior = subordinate as Superior;
    if ( subordinateAsSuperior != null )
      foreach ( Worker subordinate2 in subordinateAsSuperior.Subordinates )
        stack.Push( subordinate2 );
  }
  return salary;
}