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