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
反之不行,递归在很多编译器有层数限制。
|