递归与迭代

Question

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

Answer 1

是的，递归总是可以代替迭代，这已经讨论了before。从链接文章中引用：

因为您可以使用严格迭代结构和仅使用递归结构的Turn完成语言来构建图灵完全语言，因此这两者因此是等效的。

解释一下：我们知道任何可计算的问题都可以通过图灵机来解决。并且可以构建一个编程语言A而不用递归，这相当于一个图灵机。类似地，可以在没有迭代的情况下构建编程语言B，其计算能力等于图灵机。

因此，如果A和B都是Turing-complete，我们可以得出结论，对于任何迭代程序，都必须存在等价的递归程序，反之亦然。这是一个理论结果，因为它不会给你任何关于如何从任意迭代程序导出一个递归程序的暗示，反之亦然。

Answer 2

是的。有一种称为tail recursion的递归类型，可以直接翻译为迭代。一个可以转换成另一个没有任何问题。因此，所有迭代解决方案都可以转换为递归解决方案。实际上，许多编译器可以检测到您正在执行尾递归，然后将其转换为for循环类型的代码以提高效率。

Answer 3

当不需要循环时应使用递归，但在某种情况下该方法必须重复。例如，压缩文件夹。如果有一个子文件夹，它应该自己调用（递归）。递归可以替代迭代，如果你想，但不建议。大多数人只是使用迭代，只在需要时才使用递归。