algorithm - 在不使用递归的情况下重写递归函数

Question

我正在重写一些现有代码，其中递归调用不容易实现也不需要。（如果你必须知道的话，在 Fortran 77 中。）我考虑过从头开始制作一个堆栈来跟踪所需的调用，但这似乎很笨拙，我宁愿不为数组分配内存递归不深。（我也不相信 Fortran 77 支持动态数组大小调整。）

关于如何采用明显递归函数并以非递归方式重写它而不浪费堆栈空间的一般解决方案的任何其他建议？

非常感谢，老麦克斯特

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

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