algorithm - 递归与堆栈

Question

我想知道递归是否是解决问题的唯一方法，那么堆栈迭代是唯一的其他解决方法吗？我认为它们是等价的:如果递归有效，那么迭代肯定有效，反之亦然。

此外，我不确定为什么递归被认为是低效的并且经常导致堆栈溢出，而使用堆栈的迭代则不会。递归只是以用户不可见的自动方式使用堆栈。

Answer 1

虽然dancancode的 answer谈论不同类型的问题，例如 primitive recursive问题，recursive问题和recursively enumerable问题，恕我直言，这个问题更直接recursion或 iteration .

I wonder if recursion is the only solution to a problem, then is iteration with stacks the only other solution?

不，有很多不同的计算模型。然而，lambda calculus (递归的基础)和Turing machines (迭代的基础)是最流行的计算模型。另一个流行的计算模型是 μ-recursion .

什么是计算模型？

很长一段时间以来，数学家们都想研究计算的本质。他们想知道哪些问题可以计算(即哪些问题有解)，哪些问题不能计算(即哪些问题无解)。他们还想知道计算的性质(例如，计算相对于输入大小的解决方案需要多少时间等)。

但是，只有一个问题:“计算”是一个非常抽象的术语。你如何推理一些不具体的事情？这就是数学家需要一个他们可以推理的计算模型的原因。计算模型捕获了“计算的本质”。这意味着如果存在可以计算的问题，那么在每个计算模型中都必须有一种算法来计算它。

I think they're kind of equivalent: If recursion works, then iteration will work for sure, and vice versa.

是的，没错。 Church-Turing thesis从本质上讲，每个计算模型在功率上都是等效的。因此，您可以使用递归(即 lambda 演算)完成的所有事情也可以使用迭代(即图灵机)完成。

事实上，世界上大多数计算机都是基于图灵机的。因此，每台计算机都只使用迭代。尽管如此，您的计算机仍然可以执行递归程序。这是因为编译器将您的递归程序翻译成迭代机器代码。

Also, I'm not sure why recursion is considered inefficient and often causes stack overflows while iteration with stacks does not. Recursion just uses stacks in an automatic way invisible to the user.

这是因为操作系统处理进程的方式。大多数操作系统都对堆栈的大小施加了最大限制。在我的 Linux 操作系统上，最大堆栈大小为 8192 KB，这不是很多。使用 ulimit -s 查找 POSIX 兼容操作系统上的默认堆栈大小。这就是使用太多递归导致堆栈溢出的原因。

另一方面，堆的大小可以在进程执行时动态增加(只要有可用空间)。因此，您不必担心在使用迭代时内存不足(即使在使用显式堆栈时)。

此外，递归通常比迭代慢，因为调用函数需要 context switch而在迭代中你只需要修改指令指针(即跳转，可能是有条件的)。

然而，这并不意味着迭代总是优于递归。递归程序通常比迭代程序更小且更容易理解。此外，在某些情况下，编译器可以通过 tail call optimization 完全消除上下文切换。 (总拥有成本)。这不仅使递归与迭代一样快，而且确保堆栈大小不会增加。

有趣的是，所有的递归程序都可以通过将程序翻译成continuation-passing style 来实现尾递归。 (CPS)。因此，CPS 和 TCO 可以 eliminate the need of an implicit call stack共。一些函数式编程语言的编译器和解释器在 novel ways 中使用了这种能力.