不使用递归重写递归函数

我正在重写一些现有代码，在递归调用不容易实现也不期望的设置中。（在Fortran 77中，如果你必须知道的话）。我曾经想过要从头开始编写一个堆栈以跟踪所需的调用，但这看起来很糟糕，而且我宁愿不在内存中分配内存递归不深。（我不相信Fortran 77支持动态数组大小调整。）不使用递归重写递归函数

有关如何获取明显递归函数并在不浪费堆栈空间的情况下对其进行非递归重写的一般解决方案的其他建议？

非常感谢，老MCST

来源

2010-12-12 Old McStopher

如果它不分支，通常可以将它重写为一个简单的循环。如果它分支你通常需要一个堆栈 – CodesInChaos 2010-12-12 14:14:24

@CodeInChaos：一个不分支的递归函数，根据定义，永远不会返回... – 2010-12-12 14:18:44

猜猜我滥用词分支。我的意思是多次调用本身，所以调用的图形变成了带有分支的树。这只是我的经历，并不总是如此。 – CodesInChaos 2010-12-12 14:21:44

如果你的代码使用尾递归（也就是说，该函数返回每个递归调用的结果直接，没有任何其他处理），则有可能势在必行重写功能不会堆栈：

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

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

来源

2010-12-12 14:17:42

这与我的想法类似，但无法用语言表达。因此，在我的具体情况中，我有一组数据元素，每个元素都需要测试与该集合中其他元素的关系。我可以传入所有项目的数据结构，但由于每个项目都需要进一步处理，所以我认为堆栈是不可避免的，是的？ – 2010-12-12 14:30:45

取决于。如果代码主要是“对于所有对（a，b），如果P（a，b）是真的，那么执行F（a，b）”，你可以通过迭代循环遍历所有的对... – 2010-12-12 14:39:58

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

来源

2010-12-12 14:15:59 Ofir

小心显示一个不需要堆栈空间的递归函数？即使它的论点？ – 2010-12-12 14:28:35

@Nikita Rybak：内联尾递归函数;） – 2010-12-12 14:37:49

@Victor是的，但这是在改写的形式。 Ofir声称有一个不需要堆栈内存的递归函数。所以，我很好奇。 – 2010-12-12 15:10:06

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

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

但是，这涉及到的功能是如何工作的，不知道这是否可以推广到一个自动的过程知识。

来源

2010-12-12 16:51:54

不使用递归重写递归函数

回答

相关问题