不使用递归重写递归函数

发布于 2024-10-07 13:01:59 字数 203 浏览 2 评论 0原文

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

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

泡沫很甜 2024-10-14 13:01:59

如果您的代码使用尾递归（即函数直接返回每个递归调用的结果而不进行任何其他处理），那么可以在没有堆栈的情况下强制重写该函数：

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

Into：

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

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

If your code uses tail recursion (that is, the function returns the result of every recursive call directly without any other processing) then it's possible to rewrite the function imperatively without a stack:

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

Into:

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

Without tail recursion, using a stack (or a similar intermediary storage) is the only solution.

回复收藏 0 原文

慈悲佛祖 2024-10-14 13:01:59

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

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

但是如果没有记忆，这需要 O(N) 堆栈空间的 O(exp^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;
 }

但这涉及到函数如何工作的知识，不确定它是否可以推广到自动过程。

The classic recursive function that can be written as a loop is the Fibonacci function:

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

But without memoization this takes O(exp^N) operations with O(N) stack space.

It can be rewritten:

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

But this involves knowledge of how the function works, not sure if it can be generalized to an automatic process.

回复收藏 0 原文