当前位置：文江博客话题详情

将递归算法转换为迭代算法的设计模式

发布于 2024-08-07 14:19:26 字数 76 浏览 6 评论 0原文

是否有任何通用启发法、提示、技巧或常见设计范例可用于将递归算法转换为迭代算法？我知道这是可以做到的，我想知道这样做时是否有值得记住的做法。

原文

分享到QQ

分享到微博

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

发布评论

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

带刺的爱情 2024-08-14 14:19:26

您通常可以完全保留递归算法的原始结构，但通过使用尾调用并更改为连续传递来避免堆栈，如此博客条目。（我真的应该编写一个更好的独立示例。）

回复收藏 0 原文

回眸一笑 2024-08-14 14:19:26

我在用迭代算法替换递归算法的过程中使用的一种常用技术通常是使用堆栈，将传递给递归函数的参数推送。

查看以下文章：

回复收藏 0 原文

一笑百媚生 2024-08-14 14:19:26

常见的做法是管理一个 LIFO 堆栈，该堆栈保留“剩余要做的事情”的运行列表，并在 while 循环中处理整个过程，该循环一直持续到列表为空为止。
使用这种模式，真正的递归模型中的递归调用将被替换为
- 将当前（部分完成）任务的“上下文”推入堆栈，
- 将新任务（促使递归的任务）推入堆栈
- 并“继续”（即跳到开头）while 循环。
在循环头部附近，逻辑弹出最近插入的上下文，并在此基础上开始工作。

实际上，这只是将原本保存在“系统”堆栈上的嵌套堆栈帧中的信息“移动”到应用程序管理的堆栈容器。然而，这是一个改进，因为这个堆栈容器可以分配在任何地方（递归限制通常与“系统”堆栈中的限制相关）。因此，本质上完成了相同的工作，但“堆栈”的显式管理允许在单个循环构造中进行，而不是在递归调用中进行。

回复收藏 0 原文

仙女山的月亮 2024-08-14 14:19:26

通常，一般递归可以用尾递归代替，通过在累加器中收集部分结果并通过递归调用将其向下传递。尾递归本质上是迭代，递归调用可以实现为跳转。

例如，阶乘的标准通用递归定义

factorial(n) = if n = 0 then 1 else n * factorial(n - 1)

可以替换为

 factorial(n) = f_iter(n, 1)

and ，

 f_iter(n, a) = if n = 0 then a else f_iter(n - 1, n * a)

它是尾递归的。它是一样的

a = 1;
while (n != 0) {
    a = n * a;
    n = n - 1;
}
return a;

Often general recursion can be replaced by tail recursion, by collecting partial results in an accumulator and passing it down with the recursive call. Tail recursion is essentially iterative, the recursive call can be implemented as a jump.

For example, the standard general recursive definition of factorial

factorial(n) = if n = 0 then 1 else n * factorial(n - 1)

can be replaced by

 factorial(n) = f_iter(n, 1)

and

 f_iter(n, a) = if n = 0 then a else f_iter(n - 1, n * a)

which is tail recursive. It is the same as

a = 1;
while (n != 0) {
    a = n * a;
    n = n - 1;
}
return a;

回复收藏 0 原文

反目相谮 2024-08-14 14:19:26

查看这些链接以获取性能示例

递归 VS 迭代（循环）：速度和速度内存比较

和

用迭代替换递归

和

递归与迭代

问：通常是递归版本
快点？
答：不——它通常会比较慢（由于维护的开销）
堆栈）
 问：递归版本通常使用的内存较少吗？
  答：不会——它通常会使用更多的内存（用于堆栈）。

  问：那为什么要用递归呢？
  答：有时编写递归版本会更简单（但是
我们需要等到
讨论树看确实不错
示例...）

Have a look at these links for performance examples

Recursion VS Iteration (Looping) : Speed & Memory Comparison

and

Replace Recursion with Iteration

and

Recursion vs Iteration

Q: Is the recursive version usually
faster?
A: No -- it's usually slower (due to the overhead of maintaining
the stack)
  Q: Does the recursive version usually use less memory?
  A: No -- it usually uses more memory (for the stack).

  Q: Then why use recursion??
  A: Sometimes it is much simpler to write the recursive version (but
we'll need to wait until we've
discussed trees to see really good
examples...)

回复收藏 0 原文

我不会写诗 2024-08-14 14:19:26

我通常从基本情况开始（每个递归函数都有一个）并向后工作，如有必要，将结果存储在缓存（数组或哈希表）中。

递归函数通过解决较小的子问题并使用它们来解决较大的问题实例来解决问题。每个子问题也被进一步分解，依此类推，直到子问题很小以至于解决方案变得微不足道（即基本情况）。

这个想法是从基本案例（或多个基本案例）开始，并使用它来构建更大案例的解决方案，然后使用它们来构建更大的案例，依此类推，直到整个问题得到解决。这不需要堆栈，并且可以通过循环来完成。

一个简单的例子（Python）：

#recursive version
def fib(n):
     if n==0 or n==1:
             return n
     else:
             return fib(n-1)+fib(n-2)

#iterative version
def fib2(n):
     if n==0 or n==1:
             return n
     prev1,prev2=0,1 # start from the base case
     for i in xrange(n):
             cur=prev1+prev2 #build the solution for the next case using the previous solutions
             prev1,prev2=cur,prev1
     return cur

I generally start from the base case (every recursive function has one) and work my way backwards, storing the results in a cache (array or hashtable) if necessary.

Your recursive function solves a problem by solving smaller subproblems and using them to solve the bigger the instance of the problem. Each subproblem is also broken down further and so on until the subproblem is so small that the solution is trivial (i.e. the base case).

The idea is to start at the base case(or base cases) and use that to build the solution for larger cases, and then use those to build even larger cases and so on, until the whole problem is solved. This does not require a stack, and can be done with loops.

A simple example (in Python):

#recursive version
def fib(n):
     if n==0 or n==1:
             return n
     else:
             return fib(n-1)+fib(n-2)

#iterative version
def fib2(n):
     if n==0 or n==1:
             return n
     prev1,prev2=0,1 # start from the base case
     for i in xrange(n):
             cur=prev1+prev2 #build the solution for the next case using the previous solutions
             prev1,prev2=cur,prev1
     return cur

回复收藏 0 原文