递归与堆栈 [英] Recursion vs. Stack

问题描述

我想知道递归是否是问题的唯一解决方案，那么使用堆栈进行迭代是否是唯一的其他解决方案？我认为它们是等效的：如果递归有效，那么迭代肯定会起作用，反之亦然。

I wonder if recursion is the only solution to a problem, then is iteration with stacks the only other solution? I think they're kind of equivalent: If recursion works, then iteration will work for sure, and vice versa.

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

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.

推荐答案

尽管 dancancode 的 answer 讨论了诸如原始递归问题，递归问题和递归可枚举问题，恕我直言，这个问题是有关简单的递归或迭代。

Although dancancode's answer talks about different kinds of problems like primitive recursive problems, recursive problems and recursively enumerable problems, IMHO this question is more about straightforward recursion or iteration.

我想知道递归是否是唯一的解决方案问题，那是ite唯一可行的解​​决方案是？

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

不，有很多不同的计算模型。但是， lambda演算（递归的基础）和车床（迭代的基础）是最受欢迎的计算模型。另一个流行的计算模型是&-递归。

No, there are a lot of different models of computation. However, the lambda calculus (the basis of recursion) and Turing machines (the basis of iteration) are the most popular models of computation. Another popular model of computation is μ-recursion.

什么是计算模型？

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

For a long time mathematicians wanted to study the nature of computation. They wanted to know which problems can be computed (i.e. which problems have a solution) and which problems cannot be computed (i.e. which problems have no solution). They also wanted to know the nature of the computation (e.g. how much time does it take to compute the solution relative to its input size, etc.).

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

However, there was just one problem: “computation” is a very abstract term. How do you reason about something that's not concrete? That's the reason mathematicians needed a model of computation which they could reason about. A model of computation captures the “essence of computation”. That means that if there's a problem which can be computed then there must be an algorithm for computing it in every model of computation.

它们是等效的：如果递归有效，则迭代肯定会起作用，反之亦然。

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

是的，这是正确的。 Church-Turing论文基本上指出，每种计算模型在功率。因此，您可以使用递归（即lambda演算）执行的所有操作也可以使用迭代（即图灵机）进行。

Yes, that's correct. The Church-Turing thesis essentially states that every model of computation is equivalent in power. Hence, everything that you can do using recursion (i.e. the lambda calculus) can also be done using iteration (i.e. a Turing machine).

实际上，世界都基于图灵机。因此，每台计算机仅使用迭代。但是，您的计算机仍可以执行递归程序。这是因为编译器将您的递归程序转换为迭代机器代码。

In fact, most computers in the world are based on the Turing machine. Hence, every computer uses iteration only. Nevertheless, your computer can still execute recursive programs. This is because a compiler translates your recursive program into iterative machine code.

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

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的操作系统上查找默认堆栈大小。这就是使用过多递归会导致堆栈溢出的原因。

This is because of the way operating systems handle processes. Most operating systems impose a maximum limit on the size of a stack. On my Linux OS the maximum stack size is 8192 KB which is not a lot. Use ulimit -s to find your default stack size on a POSIX compliant OS. This is the reason why using too much recursion causes a stack overflow.

另一方面，可以在进程执行时动态增大堆的大小（例如只要有可用空间）。因此，您不必担心在使用迭代时（甚至在使用显式堆栈时）会耗尽内存。

On the other hand, the size of the heap can be dynamically increased while the process is executing (as long as free space is available). Hence, you don't have to worry about running out of memory when using iteration (even when using an explicit stack).

此外，递归通常比迭代慢，因为调用函数需要上下文切换，而在迭代中，您只需要修改指令指针（即跳转，可能是有条件的。）

Furthermore, recursion is generally slower than iteration because calling a function requires a context switch while in iteration you only need to modify the instruction pointer (i.e. jump, possibly conditional).

但是，这并不意味着迭代总是比递归更好。递归程序通常比迭代程序更小，更易于理解。此外，在某些情况下，编译器可以通过尾部调用优化（TCO）完全消除上下文切换。

However, this doesn't mean that iteration is always better than recursion. Recursive programs are usually smaller and easier to understand than iterative programs. In addition, in certain cases the compiler can eliminate context switches altogether via tail call optimization (TCO). This not only makes recursion as fast as iteration but also ensures that the stack size doesn't increase.

有趣的是，可以通过翻译程序使所有递归程序成为尾递归。变成连续传递样式（CPS）。因此，CPS和TCO可以完全消除隐式调用堆栈的需求。一些用于函数式编程语言的编译器和解释器以新颖的方式。

Interestingly, all recursive programs can be made tail recursive by translating the program into continuation-passing style (CPS). Thus, CPS and TCO can eliminate the need of an implicit call stack altogether. Several compilers and interpreters for functional programming languages use this ability in novel ways.

这篇关于递归与堆栈的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！