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

• 資深大佬 : 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

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