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

[James369]

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

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

虽然有人用迭代解决了汉诺塔的问题，但我还是不大明白。
一些复杂的递归问题，我能想到的就是“分形图案”（比较简单的比如“雪花”）。
那么用迭代怎么来实现雪花的绘制呢？ 是否存在某些问题是迭代做不到而 只有递归可以做到的？

简单的再罗列一下问题：
1. 是否所有的递归都可以转为迭代，为什么？
2. 递归是如何转换成迭代，怎么做？

感谢给出有价值线索的朋友，我都一一点赞。
结贴。

[YouLMAO]

Yes of course

[Akashic]

记得一般语言都对尾递归有优化 直接变成循环的形式

[James369]

@YouLMAO 那请问如何用迭代来实现 汉诺塔的移动

[hxndg]

知乎。。。现成的答案。。。
话说。。。。为啥很多时候你自己就能验证的事情，非要发个帖子出来呢？

[James369]

@hxndg 我问的是所有的递归都能转成迭代，其背后的数学证明是什么？

[YouLMAO]

@Akashic
汉诺塔非递归
我们对赌十万, 胜出一方必须全数捐给联合国儿童基金会
2 天写不出来当我输
你先转账 5 万,开始倒数时间

[Origami404]

@James369 可以手动用循环实现函数调用啊，模拟栈的进出就可以了，oi/acm 以前经常用的吧。
数学原理我不是很清楚，但我觉得它们本质上都是对自身的重复，递归可能比循环跟“基本”一点？
以及我猜测您可能觉得所有循环的空间占用都是与循环次数 n 无关的，因而觉得需要栈空间的递归能写成迭代很神奇，但其实只要如上文所说的那样模拟栈就可以简单地“翻译”过去了，只不过此时循环的空间占用是与 n 有关的一个函数罢了

[favourstreet]

既然都知道栈了，我支持楼主和 6 楼赌一个；话说回来，构造性的证明不知楼主接受不？就是说我可以写个程序把所有 c 的递归转成等价的循环，我们也对赌十万……

[PythonYXY]

非递归版本汉诺塔： https://www.geeksforgeeks.org/iterative-tower-of-hanoi/
上面链接里有文字说明，有图片示例，还有 C++，C#，Java 三种语言的解答

[hxndg]

@James369
@Origami404

背后的理论基础是数学归纳法，SICP 有讲过这个东西我记得。
递归和迭代的区别是什么？想明白这个问题就知道为什么有限递归可以转换
这东西同样属于可以轻松查到的，还是那句话，直接就能验证搜索到的东西，为什么还要发个帖子出来？

[BiteTheDust]

模拟系统栈就行 递归也得有具体实现啊

[Origami404]

@hxndg
确实，看来我已经忘光了... （ lisp 白学

@James369
基本上就是找到语言结构的递归定义然后写一个递归的转换函数按结构匹配递归程序将其转换成迭代的就可以了（顺带一提多分支的递归对应的归纳法更精确地讲应该叫“结构归纳法”）

[geelaw]

任何实际做出来的递归本来就是迭代，CPU 自己执行这些命令的时候就是循环运行每个指令完成的。

[Kasumi20]

我只知道我搞了很久才把递归的归并排序用两层循环实现

[James369]

@hxndg #10 你懂说明你聪明，这样你满意了吗。

[alazysun]

可以。插一句：你可以扩大栈空间啊 /doge

[lewis89]

@Origami404 #12 看栈帧这个名字就知道了， 每一次调用就跟放电影一样，先不断入栈，然后不断出栈，本质上就是在迭代..

[James369]

@hxndg 另外你说的这个数学归纳法只是作用在自然数范围，然而递归显然适用范围更广。

[Origami404]

@James369 广义的数学归纳法是包含结构归纳法的，后者可以对树形之类的递归良基结构做归纳证明，可以去看看维基百科的数学归纳法

[Origami404]

更正：递归良基结构 --> 递归定义的良基结构

[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]

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

[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 好牛逼，舌战群雄

[zxCoder]

可以

[canwushuang]

反之不行，递归在很多编译器有层数限制。