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

Question

我正在重写一些现有代码,在这种情况下递归调用不容易实现也不需要.(在Fortran 77中,如果你必须知道的话.)我已经考虑过从头开始编写一个堆栈以跟踪所需的调用,但这看起来很糟糕,而且我宁愿不在数组中分配内存.递归并不深.(我不相信Fortran 77也支持动态数组大小.)

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

非常感谢,Old 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;
  }
}

没有尾递归,使用堆栈(或类似的中间存储)是唯一的解决方案.