algorithm - 递归与迭代

Question

我相信所有具有迭代逻辑的问题都可以使用迭代来解决，但是我们可以使用递归来解决任何问题吗？递归总能代替迭代吗？如果可以，请为您的答案提供证据。还假设我们有一个无限堆栈或者我们在图灵机上运行程序。我不在乎这个证明是不是理论上的证明。（这就是我提到图灵机的原因）

Answer 1

是的，递归总是可以替代迭代，这个之前已经讨论过了。引用链接的帖子：

因为您可以使用严格的迭代结构构建图灵完备语言，而仅使用递归结构构建图灵完备语言，所以两者是等价的。

稍微解释一下：我们知道任何可计算的问题都可以通过图灵机来解决。并且可以构建一种A无需递归的编程语言，相当于图灵机。同样，可以构建一种B无需迭代的编程语言，其计算能力与图灵机相当。

因此，如果A和B都是图灵完备的，我们可以得出结论，对于任何迭代程序，都必须存在一个等价的递归程序，反之亦然。这是一个理论上的结果，因为它没有给您任何关于如何从任意迭代程序派生一个递归程序的提示，反之亦然。

Answer 2

是的。有一种递归称为尾递归，它可以直接转化为迭代。一个可以毫无问题地转换为另一个。因此，所有迭代解决方案都可以转换为递归解决方案。

其实很多编译器都可以检测到你在做尾递归，然后为了效率把它转换成for循环类型的代码。

Answer 3

当不需要循环时应使用递归，但该方法必须在特定情况下重复自身。例如，压缩文件夹。如果有子文件夹，它应该调用自己（递归）。如果您愿意，递归可以替代迭代，但不建议这样做。大多数人只使用迭代，只在需要时使用递归。