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

[James369]

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

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

[iConnect]

while true 就是单阶递归，死循环就会爆内存，递归数学上就是多阶循环潜逃，其中必然有不少于一个的无限循环，所以不可避免的会爆内存。

所以很多语言都限制了递归的最大深度。

[lightingtime]

非常推荐 CS106B 这门课程，b 站就有，你可以配合着《 Programming Abstractions in C++》这个教材看一下递归的讲解，是一个男老师讲的。

[daxy223]

楼主是高中生吗？

[v2isgood]

基础知识要记牢哦，不要都还给老师了

[hello2060]

递归不就是高中是学的数学归纳吗？为啥会感到这么神奇

[yyfearth]

这个是基本的东西把 递归就是一个栈结构
对栈进行迭代操作直到把整个栈都消化掉就完成了
如果栈消化不掉 或者栈不够大 那就溢出了

[clrss]

CPS + trampolining

[aec4d]

当然所有的递归都能转换成迭代(完全模拟，此时时间复杂度和空间复杂度都一样)
将递归转化成迭代非常难
这里有一个 2013 年写的系列 https://blog.moertel.com/tags/recursion-to-iteration%20series.html (我正在翻译)

[passerbytiny]

递归就是一种迭代，你这标题问得相当于问“男人能不能被当成人”

[yy77]

最简单的变化办法就是把递归函数的返回值作为一个参数，在循环函数里面把它带上。

[hxndg]

@James369
呵呵，还什么“你懂说明你聪明”，你浪费自己的时间发个帖子，有这个功夫去查早就搞明白咋回事了。
知识和思考是进步的两个方面。看你的回复没有任何的思考在里面，只有不断的狡辩。
计算机的本质实际上是一种计算，是一种数学上的抽象，工程师做的是一种取舍，是目标和代价之间的平衡。
你取一个点来看，忽视了背后的基础，才会觉得好神奇，才会觉得不可理解。

如果你觉得低效的学习是你所希望的，那你大可继续如此。

[yuruizhe]

肯定啊，大一学 c 语言的时候，教材上就说了，任何递归算法都有非递归的实现形式，但出于篇幅考虑证明省略

[xxxyh]

函数的递归调用就是该函数在栈中有多个栈帧，程序只要模拟栈帧，不就可以将递归转化为迭代吗

[krixaar]

这么说吧，如果让你手算一个递归过程，你怎么算？你先得按逻辑找“最底层”那一步，这样你才能算出个初始值往里面代，然后把结果代入这个算法再算，直到算出最终结果，而算的这个过程不就是迭代么……

[julyclyde]

把“判断是否再来一遍”和“再来一遍之前的准备和之后的收尾”放在里面就是递归，放在外面就是迭代

[leimao]

我觉得吧，V2EX 这个网站很多人回帖逼格弄的太高，高端喷子太多，很多人受不了都被劝退了。

[leimao]

即便问的问题在有些人看来有些幼稚，但是大家起点背景和水平都各不相同，没啥好喷的。

[lepig]

看了楼上的几位大神回复，我发现我这个高中生不配来发帖子和大家交流。 不再同一水平线上。

[msaionyc]

@hxndg 不要这样，我觉得你可以选择更友善的沟通方式。
如果你真的觉得楼主这个帖子很傻不必发出来，你可以不点进来，没必要采取这种方式，一直问楼主为什么要发帖，是不是现在互联网已经不能接受重复的提问了
另外，不是所有人的认知水平和经历，能力都和你一样，楼主来发帖讨论问题我不认为真的值得你如此对待

[ToBeHacker]

函数调用就是在压栈啊，只要你用一个显式的栈将参数存起来就可以了