递归和循环是等价的吗？

Question

具体的说就是，
是否所有的递归都能用循环改写？
反之，是否所有的循环都能用递归改写？

主要是突然想到，c++模板中，因为所有的变量都是常量，也就是没有所谓的循环，只能用递归，但它本身又是图灵完全的，这就意味所有循环做的任务都可以改用递归来完成。
那么反之是否也成立呢？

Answer 1

一张图解决你的疑惑

如果没解决继续追问

Answer 2

理论上是可以, 但实际上递归取决于语言/系统支持的最大堆栈深度, 如果超过这个上限, 就会出现 stack overflow

Answer 3

是否所有的递归都能用循环改写？

是. 可以手工操作栈来模拟递归.

反之，是否所有的循环都能用递归改写？

是. 参考函数式编程语言.

Answer 4

在可计算性的意义上是
实际的计算过程不是

Answer 5

理论上是可以，但是实际中却不是：一般来说递归在任何情况下都可以改写成循环，而且一般效率还会有一定的提升，但是耗费的资源可能会变多。反之，一般的循环不推荐写成递归，正如上面回答的，超过最大栈深度会有stack over folw ，而且时间会慢很多。最简单的例子是菲波那切数列，当递归到50附近时，时间已经无法估量了。。。。。。