这是一个创建于 1374 天前的主题，其中的信息可能已经有所发展或是发生改变。
递归真是个神奇的计算思想，可能是计算机所特有的解决思路。
特别是在解决嵌套问题时有奇效，比如汉诺塔的移动问题（以前想半天都没想通，后来突然想通了），真是又简单又有趣。
不过递归有个隐患就是可能会导致栈溢出，而迭代却可以避免因栈的使用而导致溢出。
但是用迭代很难去思考问题，并且是否所有的递归都可以转换成迭代呢？
特别是在解决嵌套问题时有奇效，比如汉诺塔的移动问题（以前想半天都没想通，后来突然想通了），真是又简单又有趣。
不过递归有个隐患就是可能会导致栈溢出，而迭代却可以避免因栈的使用而导致溢出。
但是用迭代很难去思考问题，并且是否所有的递归都可以转换成迭代呢？
第 1 条附言 · 2021-02-18 22:55:07 +08:00
虽然有人用迭代解决了汉诺塔的问题，但我还是不大明白。
一些复杂的递归问题，我能想到的就是“分形图案”（比较简单的比如“雪花”）。
那么用迭代怎么来实现雪花的绘制呢？ 是否存在某些问题是迭代做不到而 只有递归可以做到的？
一些复杂的递归问题，我能想到的就是“分形图案”（比较简单的比如“雪花”）。
那么用迭代怎么来实现雪花的绘制呢？ 是否存在某些问题是迭代做不到而 只有递归可以做到的？
第 2 条附言 · 2021-02-19 11:16:48 +08:00
简单的再罗列一下问题：
1. 是否所有的递归都可以转为迭代，为什么？
2. 递归是如何转换成迭代，怎么做？
1. 是否所有的递归都可以转为迭代，为什么？
2. 递归是如何转换成迭代，怎么做？
第 3 条附言 · 2021-02-20 00:43:17 +08:00
感谢给出有价值线索的朋友，我都一一点赞。
结贴。
结贴。
 |
1
YouLMAO 2021-02-18 21:41:19 +08:00 via Android
Yes of course
|
 |
2
Akashic 2021-02-18 21:44:25 +08:00 via Android  1
记得一般语言都对尾递归有优化 直接变成循环的形式
|
 |
4
hxndg 2021-02-18 21:47:18 +08:00 2
知乎。。。现成的答案。。。
话说。。。。为啥很多时候你自己就能验证的事情，非要发个帖子出来呢？ |
|
6
YouLMAO 2021-02-18 21:58:10 +08:00
|
 |
7
Origami404 2021-02-18 22:18:00 +08:00 via Android
@James369 可以手动用循环实现函数调用啊，模拟栈的进出就可以了，oi/acm 以前经常用的吧。
数学原理我不是很清楚，但我觉得它们本质上都是对自身的重复，递归可能比循环跟“基本”一点？ 以及我猜测您可能觉得所有循环的空间占用都是与循环次数 n 无关的，因而觉得需要栈空间的递归能写成迭代很神奇，但其实只要如上文所说的那样模拟栈就可以简单地“翻译”过去了，只不过此时循环的空间占用是与 n 有关的一个函数罢了 |
 |
8
favourstreet 2021-02-18 22:18:41 +08:00 via Android
既然都知道栈了，我支持楼主和 6 楼赌一个；话说回来，构造性的证明不知楼主接受不？就是说我可以写个程序把所有 c 的递归转成等价的循环，我们也对赌十万……
|
 |
9
PythonYXY 2021-02-18 22:21:21 +08:00 1
非递归版本汉诺塔： https://www.geeksforgeeks.org/iterative-tower-of-hanoi/
上面链接里有文字说明，有图片示例，还有 C++，C#，Java 三种语言的解答 |
|
10
hxndg 2021-02-18 22:28:38 +08:00 1
@James369
@Origami404 背后的理论基础是数学归纳法，SICP 有讲过这个东西我记得。 递归和迭代的区别是什么？想明白这个问题就知道为什么有限递归可以转换 这东西同样属于可以轻松查到的，还是那句话，直接就能验证搜索到的东西，为什么还要发个帖子出来？ |
 |
11
BiteTheDust 2021-02-18 22:34:19 +08:00
模拟系统栈就行 递归也得有具体实现啊
|
|
12
Origami404 2021-02-18 22:40:02 +08:00 via Android
|
 |
13
geelaw 2021-02-18 22:49:41 +08:00 3
任何实际做出来的递归本来就是迭代，CPU 自己执行这些命令的时候就是循环运行每个指令完成的。
|
 |
14
Kasumi20 2021-02-18 22:53:28 +08:00
我只知道我搞了很久才把递归的归并排序用两层循环实现
|
 |
16
alazysun 2021-02-18 23:01:13 +08:00
可以。插一句：你可以扩大栈空间啊 /doge
|
 |
17
lewis89 2021-02-18 23:15:21 +08:00
@Origami404 #12 看栈帧这个名字就知道了， 每一次调用就跟放电影一样，先不断入栈，然后不断出栈，本质上就是在迭代..
|
|
19
Origami404 2021-02-18 23:56:13 +08:00 via Android
@James369 广义的数学归纳法是包含结构归纳法的，后者可以对树形之类的递归良基结构做归纳证明，可以去看看维基百科的数学归纳法
|
|
20
Origami404 2021-02-18 23:57:29 +08:00 via Android
更正：递归良基结构 --> 递归定义的良基结构
|
 |
21
iConnect 2021-02-19 00:11:26 +08:00 via Android 2
while true 就是单阶递归，死循环就会爆内存，递归数学上就是多阶循环潜逃，其中必然有不少于一个的无限循环，所以不可避免的会爆内存。
所以很多语言都限制了递归的最大深度。 |
 |
22
lightingtime 2021-02-19 00:17:45 +08:00
非常推荐 CS106B 这门课程，b 站就有，你可以配合着《 Programming Abstractions in C++》这个教材看一下递归的讲解，是一个男老师讲的。
|
 |
23
daxy223 2021-02-19 01:51:33 +08:00 via Android
楼主是高中生吗？
|
 |
24
v2isgood 2021-02-19 02:33:58 +08:00 via iPhone
基础知识要记牢哦，不要都还给老师了
|
 |
25
hello2060 2021-02-19 04:41:20 +08:00 via iPhone
递归不就是高中是学的数学归纳吗？为啥会感到这么神奇
|
 |
26
yyfearth 2021-02-19 04:42:27 +08:00
这个是基本的东西把 递归就是一个栈结构
对栈进行迭代操作直到把整个栈都消化掉就完成了 如果栈消化不掉 或者栈不够大 那就溢出了 |
 |
27
clrss 2021-02-19 07:41:56 +08:00 via iPhone 1
CPS + trampolining
|
 |
28
aec4d 2021-02-19 09:02:24 +08:00 1
当然所有的递归都能转换成迭代(完全模拟，此时时间复杂度和空间复杂度都一样)
将递归转化成迭代非常难 这里有一个 2013 年写的系列 https://blog.moertel.com/tags/recursion-to-iteration%20series.html (我正在翻译) |
 |
29
passerbytiny 2021-02-19 09:07:53 +08:00 via Android
递归就是一种迭代，你这标题问得相当于问“男人能不能被当成人”
|
 |
30
yy77 2021-02-19 09:25:09 +08:00
最简单的变化办法就是把递归函数的返回值作为一个参数，在循环函数里面把它带上。
|
|
31
hxndg 2021-02-19 10:06:02 +08:00 1
@James369
呵呵，还什么“你懂说明你聪明”，你浪费自己的时间发个帖子，有这个功夫去查早就搞明白咋回事了。 知识和思考是进步的两个方面。看你的回复没有任何的思考在里面，只有不断的狡辩。 计算机的本质实际上是一种计算，是一种数学上的抽象，工程师做的是一种取舍，是目标和代价之间的平衡。 你取一个点来看，忽视了背后的基础，才会觉得好神奇，才会觉得不可理解。 如果你觉得低效的学习是你所希望的，那你大可继续如此。 |
 |
32
yuruizhe 2021-02-19 11:25:01 +08:00 via iPhone
肯定啊，大一学 c 语言的时候，教材上就说了，任何递归算法都有非递归的实现形式，但出于篇幅考虑证明省略
|
 |
33
xxxyh 2021-02-19 11:33:10 +08:00
函数的递归调用就是该函数在栈中有多个栈帧，程序只要模拟栈帧，不就可以将递归转化为迭代吗
|
 |
34
krixaar 2021-02-19 11:45:01 +08:00
这么说吧，如果让你手算一个递归过程，你怎么算？你先得按逻辑找“最底层”那一步，这样你才能算出个初始值往里面代，然后把结果代入这个算法再算，直到算出最终结果，而算的这个过程不就是迭代么……
|
 |
35
julyclyde 2021-02-19 11:53:26 +08:00
把“判断是否再来一遍”和“再来一遍之前的准备和之后的收尾”放在里面就是递归，放在外面就是迭代
|
 |
36
leimao 2021-02-19 12:05:03 +08:00 1
我觉得吧，V2EX 这个网站很多人回帖逼格弄的太高，高端喷子太多，很多人受不了都被劝退了。
|
|
37
leimao 2021-02-19 12:07:37 +08:00
即便问的问题在有些人看来有些幼稚，但是大家起点背景和水平都各不相同，没啥好喷的。
|
 |
38
lepig 2021-02-19 12:15:08 +08:00
看了楼上的几位大神回复，我发现我这个高中生不配来发帖子和大家交流。 不再同一水平线上。
|
 |
39
msaionyc 2021-02-19 12:24:14 +08:00 via Android 1
@hxndg 不要这样，我觉得你可以选择更友善的沟通方式。
如果你真的觉得楼主这个帖子很傻不必发出来，你可以不点进来，没必要采取这种方式，一直问楼主为什么要发帖，是不是现在互联网已经不能接受重复的提问了 另外，不是所有人的认知水平和经历，能力都和你一样，楼主来发帖讨论问题我不认为真的值得你如此对待 |
 |
40
ToBeHacker 2021-02-19 12:26:21 +08:00
函数调用就是在压栈啊，只要你用一个显式的栈将参数存起来就可以了
|
 |
43
mmdsun 2021-02-19 13:22:14 +08:00 via Android
递归把计算交给计算机，归纳把计算交给人，前者是拿计算机的计算成本换人的时间，后者是拿人的时间换计算机的计算成本。
用迭代和递归都能解决问题，但是使用递归时，由于有数学归纳法保证递归关系的正确性，所以只要专注于解决 2 个相邻层的关系就可以了，然后使用数学归纳法的基本情况作为递归出口。当然，在实际编程中，递归会增加函数调用栈的开销，也是要考虑的一方面 |
 |
44
lizytalk 2021-02-19 13:40:38 +08:00
最直接的就是手动实现 stack 呗
|
 |
45
onec 2021-02-19 17:47:41 +08:00
肯定可以的，只是很多递归改起来太费脑子了
|
 |
46
stevefan1999 2021-02-19 19:03:33 +08:00 1
不能
只有 totally computable 和 primitive recursive function 才可以 是 totally computable 但不是 primitive recursive 的例子有 Ackermann function 樓主你是沒有讀過 CS 嗎 |
|
47
stevefan1999 2021-02-19 19:08:25 +08:00
補充 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)) |
 |
48
aptupdate 2021-02-19 19:15:08 +08:00 via iPhone
Java 是的，而且大部分情况下转换为迭代后效率更高。
|
 |
49
yuelang85 2021-02-19 21:49:07 +08:00
迭代就有为了优化递归而来的
|
|
50
aec4d 2021-02-19 22:18:37 +08:00 1
这篇总结感觉写的很好 https://www.v2ex.com/t/675945
|
 |
51
chendl111 2021-02-19 23:21:53 +08:00
@hxndg 每当你想要批评别人时，你要记住，这个世界上所有的人，并不是个个都有过你拥有的那些优越条件——了不起的盖茨比
|
 |
52
no1xsyzy 2021-02-20 02:00:18 +08:00
@stevefan1999 我觉得你理解错了迭代的意思……
并不一定是能事先确定循环次数才叫迭代，牛顿迭代法甚至可能不停机。有名的几个分形集都是由“迭代产生的数列是否收敛”来定义的。 |
 |
53
dd112389 2021-02-20 02:05:48 +08:00
理论上所有递归都能转换为迭代实现, 并且迭代实现效率应该会比递归高.
(抬杠说经过 xxxx 优化最后都是迭代的大可不必) |
 |
54
msg7086 2021-02-20 03:38:32 +08:00
递归在操作系统层面上就迭代。递归的时候操作系统帮你把局部变量现场保存到栈里，然后帮你跳转到程序的头部继续执行。你想要数学证明，但其实递归就是迭代的一种实现。
|
|
55
hxndg 2021-02-20 09:30:44 +08:00 via Android
|
 |
56
akatquas 2021-02-20 09:54:47 +08:00
楼主对赌 10 w 的事情有下文吗？在线等
|
|
57
akatquas 2021-02-20 09:55:51 +08:00
看错了，楼里面对赌 10 w 的事情。
|
 |
58
sakura1 2021-02-20 10:40:01 +08:00
当然可以
|
 |
59
hejw19970413 2021-02-20 11:40:51 +08:00
其实递归就是遍历的一种，只不过在这个过程中，不需要你来进行维护上一次的执行结果。递归也有好的递归和不好的递归，递归如果用不好的话，那么是非常容易出现问题的。
|
 |
61
zxCoder 2021-02-20 14:59:18 +08:00
可以
|
 |
62
canwushuang 2021-02-21 18:19:41 +08:00 via Android
反之不行，递归在很多编译器有层数限制。
|
Select Language