关于递归的一般问题

Question

据我所知，好的递归解决方案可以使复杂的问题变得更容易。无论是时间还是空间，它们都可以更高效。

我的问题是：这不是免费的，调用堆栈会非常深。它会消耗大量的内存。我对吗？

Answer 1

很难精确地确定与递归有关的折衷。

在数学抽象级别，递归提供了一个强大的框架来描述函数的显式行为。例如，我们可以用数学定义阶乘为

x! = 1    if x == 0 
x! = x * (x - 1)! else 

或者，我们可以递归定义一个更复杂的功能，比如我们如何计算“N选K”：

C(n, k) = 1        if k == 0 
C(n, k) = 0        if k < 0 or if n > k 
C(n, k) = C(n - 1, k) + C(n - 1, k - 1) else 

当使用递归作为实现技术，不能保证您最终会使用更多内存或生成更高效运行的代码。通常，递归使用更多空间是因为需要内存来保存堆栈帧，但在某些语言中，这不是问题，因为编译器可以尝试优化功能调用（例如，请参阅tail call elimination）。在其他情况下，递归可能会耗用大量资源，以至递归代码无法终止简单问题。

至于效率问题，通常递归代码的效率远低于迭代代码。函数调用很昂贵，而从递归到代码的天真转换会导致不必要的工作重复。例如，天真的斐波那契实现

int Fibonacci(int n) { 
    if (n <= 1) return n; 
    return Fibonacci(n - 1) + Fibonacci(n - 2); 
} 

是窘况效率低，速度很慢它从来没有在实践中使用。尽管代码更清晰，但效率低下可能会消除递归的任何潜在好处。

但是，在其他情况下，递归可以是一个惊人的节省时间。作为一个例子，归并是由一个美丽的递归定义的非常快的排序算法：

Mergesort(array, low, high) { 
    if (low >= high - 1) return; 
    Mergesort(array, low, low + (high - low)/2); 
    Mergesort(array, low + (high - low)/2, high); 
    Merge(array, low, low + (high - low)/2, high); 
} 

此代码是极其快速和相应的迭代码可能会比较慢，难以阅读，并且更难理解。

因此，简而言之，递归既不是一种魔法疗法，也不是一种可以避免的力量。它有助于说明许多问题的结构，否则这些问题似乎很难或几乎不可能。虽然它通常会导致更清晰的代码，但它通常是以牺牲时间和内存为代价的（尽管它不一定会自动降低效率;在许多情况下效率可能更高）。即使您从不在您的生活中编写另一个递归函数，但仍然值得研究以改善您的整体算法思维和解决问题的能力。

希望这会有所帮助！

Answer 2

Cons: 
It is hard (especially for inexperienced programmers) to think recursively 
There also exists the problem of stack overflow when using some forms of recursion (head 
recursion). 
It is usually less efficient because of having to push and pop recursions on and off the 
run-time stack, so it can be slower to run than simple iteration. 

但是，为什么我们打扰使用递归？

Pros: 
It is easier to code a recursive solution once one is able to identify that solution. The 
recursive code is usually smaller, more concise, more elegant, and possibly even easier to 
understand, though that depends on one’s thinking style☺ 
There are some problems that are very difficult to solve without recursion. Those problems 
that require backtracking such as searching a maze for a path to an exit or tree based 
operations are best solved recursively. 

Answer 3

实际上调用堆栈不会很深。例如，像quicksort这样的分而治之的算法将问题分成两半。使用深度为32的调用堆栈，可以对4G元素进行排序，这可能甚至不适合普通计算机的内存。内存消耗并不是真正的问题，它是一个堆栈，只要你没有用完，它就是免费的。（并且有32个级别，你需要在每个级别存储大量数据）。

如果您将堆栈结构中的堆栈上的状态保留在堆栈结构中，那么您几乎可以将所有的回收过程重写为迭代过程，但这只会使代码复杂化。通过重写可以获得真正好处的主要场景是当您有一个尾递归代码时，不需要为每次递归调用维护状态。请注意，对于某些语言（大多数函数式编程语言和C/C++，也可能是Java），优秀的编译器可以为您执行此操作。

Answer 4

这取决于。递归最适合的问题将抵抗这个问题。一个常见的例子是Mergesort，其中为了排序N个项目的列表，将会有大约log2（N）个堆栈帧。因此，如果您的堆栈限制为200，并且您在调用Mergesort时已经使用了50，那么仍然足以在没有堆栈溢出的情况下对大约2^150个物品进行排序。另外，Mergesort不会为每个堆栈帧创建大量内存，因此Mergesort的总内存使用永远不会超过原始列表大小的两倍。

此外，一些语言（Scheme是一个很好的例子）使用tail-call elimination，这样代码可以使用递归优雅地编写，但优化或编译成迭代循环。这是LISP作为函数式语言在执行速度方面仍然能够与C和C++竞争的方式之一。

还有另一种技术Trampolining，可以用来执行看似递归操作而不产生深度调用堆栈。但是，除非它是建立在图书馆或甚至是语言层次的构建中，否则这种技术在生产力方面的优势不那么明显（在我看来）。

所以虽然在很多情况下很难与好的旧版for x in xrange(10)循环争论，但递归确实有它的位置。

Answer 5

如果您的递归不是尾递归，而且您的语言不支持尾递归，那它只是很贵。看到尾调用下面的Wikipedia文章关于这个问题的讨论：

http://en.wikipedia.org/wiki/Tail_call

否则，它可以使代码更容易阅读和易于测试。

Answer 6

这取决于问题。

如果问题需要递归，就像深度优先树遍历一样，唯一可以避免递归的方法是通过编写自己的堆栈来模拟它。这不会保存任何东西。

如果问题不需要递归，就像通常的Ho-Hum因子或Fibonacci函数一样，那有什么意义呢？你没有获得任何使用它。

这是一个相当小的问题，你甚至可能有一个合理的选择。