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

[James369]

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

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

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

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