任何的递归调用都可以转换为迭代吗？

[James369]

递归真是个神奇的计算思想，可能是计算机所特有的解决思路。
特别是在解决嵌套问题时有奇效，比如汉诺塔的移动问题（以前想半天都没想通，后来突然想通了），真是又简单又有趣。

不过递归有个隐患就是可能会导致栈溢出，而迭代却可以避免因栈的使用而导致溢出。
但是用迭代很难去思考问题，并且是否所有的递归都可以转换成迭代呢？

[leimao]

@msaionyc 所以我现在只发娱乐休闲帖了 XD

[msaionyc]

@leimao 说难听一点，我觉得部分人有点清高得过分了

[mmdsun]

递归把计算交给计算机，归纳把计算交给人，前者是拿计算机的计算成本换人的时间，后者是拿人的时间换计算机的计算成本。

用迭代和递归都能解决问题，但是使用递归时，由于有数学归纳法保证递归关系的正确性，所以只要专注于解决 2 个相邻层的关系就可以了，然后使用数学归纳法的基本情况作为递归出口。当然，在实际编程中，递归会增加函数调用栈的开销，也是要考虑的一方面

[lizytalk]

最直接的就是手动实现 stack 呗

[onec]

肯定可以的，只是很多递归改起来太费脑子了

[stevefan1999]

不能
只有 totally computable 和 primitive recursive function 才可以
是 totally computable 但不是 primitive recursive 的例子有 Ackermann function

樓主你是沒有讀過 CS 嗎

[stevefan1999]

補充 Ackermann function 的 wiki: https://en.wikipedia.org/wiki/Ackermann_function
另外 Ackermann 的逆 a(n)應該很多人刷 OJ 知道吧 就是栗子有 union find 的尋祖問題就是 O((log.log.log...log)(n)) = O(a(n))

[aptupdate]

Java 是的，而且大部分情况下转换为迭代后效率更高。

[yuelang85]

迭代就有为了优化递归而来的

[aec4d]

这篇总结感觉写的很好 https://www.v2ex.com/t/675945

[chendl111]

@hxndg 每当你想要批评别人时，你要记住，这个世界上所有的人，并不是个个都有过你拥有的那些优越条件——了不起的盖茨比

[no1xsyzy]

@stevefan1999 我觉得你理解错了迭代的意思……
并不一定是能事先确定循环次数才叫迭代，牛顿迭代法甚至可能不停机。有名的几个分形集都是由“迭代产生的数列是否收敛”来定义的。

[dd112389]

理论上所有递归都能转换为迭代实现, 并且迭代实现效率应该会比递归高.
(抬杠说经过 xxxx 优化最后都是迭代的大可不必)

[msg7086]

递归在操作系统层面上就迭代。递归的时候操作系统帮你把局部变量现场保存到栈里，然后帮你跳转到程序的头部继续执行。你想要数学证明，但其实递归就是迭代的一种实现。

[hxndg]

@chendl111
@msaionyc
@msaionyc
@lepig
就连引用名人名言的都出来了……所以就连百度一下都成为了很高的门槛呗，呵呵，你们的友善真普世啊。

lz 的问题非常精确，不是开放式问题，不需要任何开放式的回答。他原先的问题就有这种查查资料就能明白的问题，那他进步了吗？你们的友善除了让人舒服真的能起作用吗？

普世价值观在工程和学术上没用

[akatquas]

楼主对赌 10 w 的事情有下文吗？在线等

[akatquas]

看错了，楼里面对赌 10 w 的事情。

[sakura1]

当然可以

[hejw19970413]

其实递归就是遍历的一种，只不过在这个过程中，不需要你来进行维护上一次的执行结果。递归也有好的递归和不好的递归，递归如果用不好的话，那么是非常容易出现问题的。

[heyhumor]

@hxndg 好牛逼，舌战群雄