在不使用递归的情况下重写递归功能

Question

我正在重写一些现有的代码，即递归调用不容易实现或不需要。 （在Fortran 77中，如果您必须知道。）我考虑过从头开始堆栈以跟踪所需的电话，但这似乎是Kludgy，我宁愿在情况下分配内存递归不是很深的。 （我不相信Fortran 77也支持动态阵列尺寸。）

关于如何采用明显的递归功能并非捕获的情况下，没有浪费空间在堆栈上，有其他建议吗？

非常感谢，老MCST

Answer 1

如果您的代码使用尾部递归（即，该函数将直接返回每个递归调用的结果而无需任何其他处理），则可以在没有堆栈的情况下迫切地重写该功能：

function dosomething(a,b,c,d) 
{
  // manipulate a,b,c,d
  if (condition) 
    return dosomething(a,b,c,d) 
  else
    return something;
}

进入：

function dosomething(a,b,c,d) 
{
  while (true) 
  {
    // manipulate a,b,c,d
    if (condition) continue;
    else return something;
  }
}

没有尾部递归，使用堆栈（或类似的中介存储）是唯一的解决方案。

Answer 2

可以写入循环的经典递归函数是斐波那契函数：

 function fib(n)
 {
     // valid for n >= 0
     if (n < 2)
         return n;
     else
         return fib(n-1) + fib(n-2);
 }

但是，如果没有回忆，这需要O（exp^n）的操作，并带有O（n）堆栈空间。

它可以重写：

 function fib(n)
 {
     if (n < 2)
        return n;
     var a = 0, b = 1;
     while (n > 1)
     {
         var tmp = a;
         a = b;
         b = b + tmp;
         n = n - 1;
     }   
     return b;
 }

但这涉及有关功能如何工作的知识，不确定是否可以将其推广到自动过程。

Answer 3

大多数递归功能可以轻松地重写为循环，以浪费空间 - 取决于功能，因为许多（但不是全部）递归算法实际上取决于这种存储（尽管在这些情况下，循环版本通常更有效也）。