何时使用递归而不是迭代？ [英] When to use recursion instead of iteration?

问题描述

我想知道是否有些情况下使用递归可能比迭代更好或反过来？



我尝试过：



我知道理论上几乎（？）任何可以通过递归完成的事情也可以通过迭代完成，反之亦然。我还认为，从计算上讲，递归效率较低。但是我想问哪个更纯粹是为了简化代码并使开发人员的工作变得更容易？

I was wondering if there are some cases when using recursion might be better than iteration or the other way around?

What I have tried:

I know that theoretically almost(?) anything that can be done with recursion can also be done with iteration and vice versa. I also think that, computationally, recursion is less efficient. but I'm asking which is better purely for the purpose of simplifying the code and making the developer's job easier?

推荐答案

与迭代相比，递归很少是更好的选择。

在处理递归定义的数据结构（已知有限大小！）的某些问题的情况下可能更容易理解。



然而，存在一些难以表现为迭代的问题。考虑（纯粹学术性的）Ackermann-Péter函数：

Recursion is rarely the better choice compared with iteration.
It might be more understandable in cases of some problems dealing with recursively defined data structures (that are known to be bounded size!).

However there are some problems that would be insanely difficult to represent as iteration. Consider the (purely academic) Ackermann–Péter function:

A(m, n) where m >= 0, n >= 0
  => n + 1                   if m == 0
  => A(m - 1, 1)             if m > 0 and n == 0
  => A(m - 1, A(m, n - 1))   if m > 0 and n > 0

尝试将此结构化为迭代将非常困难。

（这也是计算上巨大的.A（4,2）有19729十进制数字。）



现在你不太可能不得不处理这个深奥的东西，所以当它使代码的意图更多时，我会选择递归很明显，它是有界限的，并且相对于迭代的任何计算效率低对整个应用程序来说并不重要。



注意许多优化编译器可以转换尾递归进入迭代实现！

oldie-goldie Wirth的书籍 [ ^ ]提供对这一论点的深刻见解。

The oldie-goldie Wirth's book[^] provides excellent insight on this very argument.

确实，在实践中，递归很少是更好的选择（解决方案1，由Matt T Heffron提供）。



马特的解释和理由是正确和合理的，但在某种程度上它们可以概括。



有些问题本质上是递归的。因此，通过正式编程递归表达的这类问题的解决方案总是易于创建，理解，调试和维护。

理解递归的概念在广义上理解 vs。一些特定于计算的含义：

递归 - 维基百科，免费的百科全书 [ ^ ]，

递归（计算机科学） - 维基百科，免费的百科全书 [ ^ ]。



所以递归的好处解决方案肯定是易于编程。但这够了吗？否。递归解决方案至少应该是可接受的：1）性能，2）所需的内存量;重要的是要了解内存需求总是减少到可以同时创建多少堆栈帧，直到抛出堆栈溢出异常为止。



对于迭代解决方案，主要标准是编程问题，如解决方案1中所述，性能和内存要求比递归要宽松得多。



让我们考虑两个递归示例，一个是递归解决方案的错误选择，一个是好的。



第一个 是 factorial 。实际上，这是递归解决方案的一个流行的例子。可能，在计算机科学教学不好（也非常普遍）的情况下，这是一个旨在完全谴责递归的最有效的例子。 :-)这是一种选择递归解决方案最糟糕的例子的方法，并产生错误的印象，即递归总是错误的。实际上，因子计算的迭代解决方案甚至比递归更简单;并且迭代解决方案比递归无限好。这些人的逻辑真的很棒。



第二个例子 是我最喜欢的例子递归真的很好。想象一下，您必须使用一些元数据来建模一些类层次结构。您可能拥有一组类，需要遍历继承层次结构。它可能与反射有关;不要紧。使用反射，用于表示类的每个set元素可以是类型元数据类的实例，例如.NET System.Type 实例，但它可以是其他任何内容。在这样的集合上解决的问题的一个例子是一些代码或伪代码生成，要求每个类声明应该放在其父类的声明之下（这是某些语言如C ++的要求）。使用递归，这根本不是问题。您获取每个当前类的基类（如果有），并递归调用将声明附加到输出字符串的函数。这样，无论输入的顺序是什么，输出声明的顺序总是保留。



为什么在这种情况下递归比另一种方法更好？因为您根本不打扰订单，所以它会自动保留。为什么性能内存消耗和堆栈溢出不会产生任何问题？因为我们只需要处理几乎合理的类层次结构，这可能会被编译，等等。这种层次结构的深度在物理上不太可能高到为堆栈和堆栈存储器提出任何问题。实际上，递归的编程的简易性带来了很多好处（尽管仍然可以使用非递归解决方案），并且性能和内存消耗问题不存在任何问题。







我差点忘了提及尾递归的重要性（也在提到解决方案1），递归的一种特殊情况，其中实现（例如，特定编译器或代码优化器）可以通过用跳转替换实际调用来避免添加堆栈帧。这种技术称为尾部调用消除，可用于递归的基本优化，这使得该解决方案非常有效：尾巴召唤 - 维基百科，免费的百科全书 [ ^ ]。

-SA

True, in practice, recursion is rarely the better choice (Solution 1, by Matt T Heffron).

Matt's explanation and rationale are correct and reasonable, but they can be generalized, to certain extent.

There are problems which are recursive by their nature. Therefore, the solution of such problems expressed through formal programming recursion is always easy to create, understand, debug and maintain.
It's good to understand the concept of recursion in the wide sense of this word vs. some meaning specific to computing:
Recursion — Wikipedia, the free encyclopedia[^],
Recursion (computer science) — Wikipedia, the free encyclopedia[^].

So the benefit of a recursive solution is certain "ease of programming". But is it enough? No. The recursive solution should be at least acceptable in terms of 1) performance, 2) the amount of memory required; it's important to understand that the memory requirements are always reduced to how many stack frames can be created at the same time until stack overflow exception is thrown.

For an iterative solution the major criteria is the programming problem, as explained in Solution 1, and performance and memory requirements are much more relaxed than with recursion.

Let's consider two recursive examples, one is a bad choice for a recursive solution, and one is good.

First one is factorial. Actually, this is a popular example of recursive solution. Probably, in bad (and very widespread) computer science teaching, this is the most efficient example aimed to denounce recursion completely. :-) It's a way to choose the worst example of a recursive solution and create a false impression that recursion is always wrong. Indeed, the iterative solution for the factorial calculation is even simpler than recursive; and the iteration solution is infinitely better than recursive. The logic of such people is truly amazing.

The second example is my all-time favorite example where recursion is really good. Imagine that you have to model some class hierarchy using some metadata. You may have the set of classes and need to walk the inheritance hierarchy. It can be related to reflection or not; it does not matter. With reflection, each set element used to represent a class could be the instance of the type metadata class, such as .NET System.Type instance, but it could be anything else. One of the example of the problem solved on such set is some code or pseudo-code generation with the requirement that each class declaration should be placed below the declaration of its parent class (which is a requirement for some languages like C++). With recursive, this is not a problem at all. You take the base class(es) of each current class, if any, and recursively call the function appending the declaration to your output string. This way, the order of output declaration is always preserved, no matter what is the order on input.

Why is recursion much better in this case than another approach? Because you don't bother about order at all, it is preserved automatically. Why won't performance memory consumption and stack overflow make any issues? Because we only need to handle practically sensible class hierarchies, which would probably be compiled, and so on. The depth of such hierarchy physically are unlikely to be so high as to present any problems for the stack and stack memory. Effectively, "ease of programming" of recursions gives a lot of benefits (despite the fact that a non-recursive solution is still possible), and the issues of performance and memory consumption don't present any problems.



I almost forgot to mention the importance of tail recursion (also mentioned in Solution 1), a special case of recursion where the implementation (say, of a particular compiler or code optimizer) can avoid adding stack frames by replacement of actual calls with jumps. This technique is called tail call elimination and can be used for radical optimization of recursion, which makes the solution extremely efficient: Tail call — Wikipedia, the free encyclopedia[^].

—SA

这篇关于何时使用递归而不是迭代？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！