language-agnostic - 关于递归的一般问题

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

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

至于效率问题，递归代码通常比迭代代码效率低得多。函数调用代价高昂，而且从递归到代码的简单转换会导致不必要的重复工作。例如，朴素的斐波那契实现

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

这段代码非常快，相应的迭代代码可能会更慢、更难阅读、更难理解。

因此，简而言之，递归既不是 Elixir ，也不是一种可以避免的力量。它有助于阐明许多问题的结构，否则这些问题可能看起来很困难或几乎不可能。虽然它通常会导致代码更清晰，但它通常会以时间和内存为代价(尽管它不一定会自动降低效率；在许多情况下它可以更有效)。即使您一生中从未编写过另一个递归函数，也绝对值得学习以提高您的整体算法思维和解决问题的能力。

希望这可以帮助!