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;
  }
}

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