关于递归的一般问题

Question

据我所知,良好的递归解决方案可以使复杂的问题变得更容易.它们在时间或空间方面都更有效.

我的问题是:这不是免费的,调用堆栈将非常深.它会占用大量内存.我对吗？

Answer 1

很难准确地确定递归所涉及的权衡.

在数学上抽象的层次上,递归提供了一个强大的框架来描述函数的显式行为.例如,我们可以在数学上将阶乘定义为

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

或者我们可以递归地定义一个更复杂的函数,例如我们如何计算"N choose 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

使用递归作为实现技术时,无法保证最终会使用更多内存或生成运行效率更高的代码.通常情况下,递归使用更多的空间,因为持有堆栈帧所需的内存,但在某些语言中,这是不是因为编译器可以尝试优化掉函数调用(参见,例如,尾部调用消除)的问题.在其他情况下,递归可能会占用大量资源,以至于递归代码无法在简单问题上终止.

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

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

极其低效且速度太快,从未在实践中使用过.虽然代码更清晰,但效率低下会消除递归的任何潜在好处.

但在其他情况下,递归可以节省大量时间.例如,mergesort是一种非常快速的排序算法,由一个漂亮的递归定义:

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

此代码非常快,相应的迭代代码可能更慢,更难阅读,更难理解.

因此,简而言之,递归既不是一种神奇的治愈方法,也不是一种可以避免的力量.它有助于阐明许多问题的结构,否则这些问题似乎很难或几乎不可能.虽然它通常会导致更清晰的代码,但它通常以牺牲时间和内存为代价(尽管它不一定自动效率较低;在许多情况下它可能更有效).这绝对是值得我们学习,以提高你的整体算法思维和解决问题的能力,即使你从来不写在你的生活另一个递归函数.

希望这可以帮助!