V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
James369
V2EX  ›  程序员

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

  •  
  •   James369 · 2021-02-18 21:39:38 +08:00 · 6161 次点击
    这是一个创建于 1359 天前的主题,其中的信息可能已经有所发展或是发生改变。
    递归真是个神奇的计算思想,可能是计算机所特有的解决思路。
    特别是在解决嵌套问题时有奇效,比如汉诺塔的移动问题(以前想半天都没想通,后来突然想通了),真是又简单又有趣。

    不过递归有个隐患就是可能会导致栈溢出,而迭代却可以避免因栈的使用而导致溢出。
    但是用迭代很难去思考问题,并且是否所有的递归都可以转换成迭代呢?
    第 1 条附言  ·  2021-02-18 22:55:07 +08:00
    虽然有人用迭代解决了汉诺塔的问题,但我还是不大明白。
    一些复杂的递归问题,我能想到的就是“分形图案”(比较简单的比如“雪花”)。
    那么用迭代怎么来实现雪花的绘制呢? 是否存在某些问题是迭代做不到而 只有递归可以做到的?
    第 2 条附言  ·  2021-02-19 11:16:48 +08:00
    简单的再罗列一下问题:
    1. 是否所有的递归都可以转为迭代,为什么?
    2. 递归是如何转换成迭代,怎么做?
    第 3 条附言  ·  2021-02-20 00:43:17 +08:00
    感谢给出有价值线索的朋友,我都一一点赞。
    结贴。
    62 条回复    2021-02-21 18:19:41 +08:00
    YouLMAO
        1
    YouLMAO  
       2021-02-18 21:41:19 +08:00 via Android
    Yes of course
    Akashic
        2
    Akashic  
       2021-02-18 21:44:25 +08:00 via Android   ❤️ 1
    记得一般语言都对尾递归有优化 直接变成循环的形式
    James369
        3
    James369  
    OP
       2021-02-18 21:44:42 +08:00
    @YouLMAO 那请问如何用迭代来实现 汉诺塔的移动
    hxndg
        4
    hxndg  
       2021-02-18 21:47:18 +08:00   ❤️ 2
    知乎。。。现成的答案。。。
    话说。。。。为啥很多时候你自己就能验证的事情,非要发个帖子出来呢?
    James369
        5
    James369  
    OP
       2021-02-18 21:56:59 +08:00
    @hxndg 我问的是所有的递归都能转成迭代,其背后的数学证明是什么?
    YouLMAO
        6
    YouLMAO  
       2021-02-18 21:58:10 +08:00
    @Akashic
    汉诺塔非递归
    我们对赌十万, 胜出一方必须全数捐给联合国儿童基金会
    2 天写不出来当我输
    你先转账 5 万,开始倒数时间
    Origami404
        7
    Origami404  
       2021-02-18 22:18:00 +08:00 via Android
    @James369 可以手动用循环实现函数调用啊,模拟栈的进出就可以了,oi/acm 以前经常用的吧。
    数学原理我不是很清楚,但我觉得它们本质上都是对自身的重复,递归可能比循环跟“基本”一点?
    以及我猜测您可能觉得所有循环的空间占用都是与循环次数 n 无关的,因而觉得需要栈空间的递归能写成迭代很神奇,但其实只要如上文所说的那样模拟栈就可以简单地“翻译”过去了,只不过此时循环的空间占用是与 n 有关的一个函数罢了
    favourstreet
        8
    favourstreet  
       2021-02-18 22:18:41 +08:00 via Android
    既然都知道栈了,我支持楼主和 6 楼赌一个;话说回来,构造性的证明不知楼主接受不?就是说我可以写个程序把所有 c 的递归转成等价的循环,我们也对赌十万……
    PythonYXY
        9
    PythonYXY  
       2021-02-18 22:21:21 +08:00   ❤️ 1
    非递归版本汉诺塔: https://www.geeksforgeeks.org/iterative-tower-of-hanoi/
    上面链接里有文字说明,有图片示例,还有 C++,C#,Java 三种语言的解答
    hxndg
        10
    hxndg  
       2021-02-18 22:28:38 +08:00   ❤️ 1
    @James369
    @Origami404

    背后的理论基础是数学归纳法,SICP 有讲过这个东西我记得。
    递归和迭代的区别是什么?想明白这个问题就知道为什么有限递归可以转换
    这东西同样属于可以轻松查到的,还是那句话,直接就能验证搜索到的东西,为什么还要发个帖子出来?
    BiteTheDust
        11
    BiteTheDust  
       2021-02-18 22:34:19 +08:00
    模拟系统栈就行 递归也得有具体实现啊
    Origami404
        12
    Origami404  
       2021-02-18 22:40:02 +08:00 via Android
    @hxndg
    确实,看来我已经忘光了... ( lisp 白学

    @James369
    基本上就是找到语言结构的递归定义然后写一个递归的转换函数按结构匹配递归程序将其转换成迭代的就可以了(顺带一提多分支的递归对应的归纳法更精确地讲应该叫“结构归纳法”)
    geelaw
        13
    geelaw  
       2021-02-18 22:49:41 +08:00   ❤️ 3
    任何实际做出来的递归本来就是迭代,CPU 自己执行这些命令的时候就是循环运行每个指令完成的。
    Kasumi20
        14
    Kasumi20  
       2021-02-18 22:53:28 +08:00
    我只知道我搞了很久才把递归的归并排序用两层循环实现
    James369
        15
    James369  
    OP
       2021-02-18 22:56:38 +08:00   ❤️ 1
    @hxndg #10 你懂说明你聪明,这样你满意了吗。
    alazysun
        16
    alazysun  
       2021-02-18 23:01:13 +08:00
    可以。插一句:你可以扩大栈空间啊 /doge
    lewis89
        17
    lewis89  
       2021-02-18 23:15:21 +08:00
    @Origami404 #12 看栈帧这个名字就知道了, 每一次调用就跟放电影一样,先不断入栈,然后不断出栈,本质上就是在迭代..
    James369
        18
    James369  
    OP
       2021-02-18 23:34:52 +08:00
    @hxndg 另外你说的这个数学归纳法只是作用在自然数范围,然而递归显然适用范围更广。
    Origami404
        19
    Origami404  
       2021-02-18 23:56:13 +08:00 via Android
    @James369 广义的数学归纳法是包含结构归纳法的,后者可以对树形之类的递归良基结构做归纳证明,可以去看看维基百科的数学归纳法
    Origami404
        20
    Origami404  
       2021-02-18 23:57:29 +08:00 via Android
    更正:递归良基结构 --> 递归定义的良基结构
    iConnect
        21
    iConnect  
       2021-02-19 00:11:26 +08:00 via Android   ❤️ 2
    while true 就是单阶递归,死循环就会爆内存,递归数学上就是多阶循环潜逃,其中必然有不少于一个的无限循环,所以不可避免的会爆内存。

    所以很多语言都限制了递归的最大深度。
    lightingtime
        22
    lightingtime  
       2021-02-19 00:17:45 +08:00
    非常推荐 CS106B 这门课程,b 站就有,你可以配合着《 Programming Abstractions in C++》这个教材看一下递归的讲解,是一个男老师讲的。
    daxy223
        23
    daxy223  
       2021-02-19 01:51:33 +08:00 via Android
    楼主是高中生吗?
    v2isgood
        24
    v2isgood  
       2021-02-19 02:33:58 +08:00 via iPhone
    基础知识要记牢哦,不要都还给老师了
    hello2060
        25
    hello2060  
       2021-02-19 04:41:20 +08:00 via iPhone
    递归不就是高中是学的数学归纳吗?为啥会感到这么神奇
    yyfearth
        26
    yyfearth  
       2021-02-19 04:42:27 +08:00
    这个是基本的东西把 递归就是一个栈结构
    对栈进行迭代操作直到把整个栈都消化掉就完成了
    如果栈消化不掉 或者栈不够大 那就溢出了
    clrss
        27
    clrss  
       2021-02-19 07:41:56 +08:00 via iPhone   ❤️ 1
    CPS + trampolining
    aec4d
        28
    aec4d  
       2021-02-19 09:02:24 +08:00   ❤️ 1
    当然所有的递归都能转换成迭代(完全模拟,此时时间复杂度和空间复杂度都一样)
    将递归转化成迭代非常难
    这里有一个 2013 年写的系列 https://blog.moertel.com/tags/recursion-to-iteration%20series.html (我正在翻译)
    passerbytiny
        29
    passerbytiny  
       2021-02-19 09:07:53 +08:00 via Android
    递归就是一种迭代,你这标题问得相当于问“男人能不能被当成人”
    yy77
        30
    yy77  
       2021-02-19 09:25:09 +08:00
    最简单的变化办法就是把递归函数的返回值作为一个参数,在循环函数里面把它带上。
    hxndg
        31
    hxndg  
       2021-02-19 10:06:02 +08:00   ❤️ 1
    @James369
    呵呵,还什么“你懂说明你聪明”,你浪费自己的时间发个帖子,有这个功夫去查早就搞明白咋回事了。
    知识和思考是进步的两个方面。看你的回复没有任何的思考在里面,只有不断的狡辩。
    计算机的本质实际上是一种计算,是一种数学上的抽象,工程师做的是一种取舍,是目标和代价之间的平衡。
    你取一个点来看,忽视了背后的基础,才会觉得好神奇,才会觉得不可理解。

    如果你觉得低效的学习是你所希望的,那你大可继续如此。
    yuruizhe
        32
    yuruizhe  
       2021-02-19 11:25:01 +08:00 via iPhone
    肯定啊,大一学 c 语言的时候,教材上就说了,任何递归算法都有非递归的实现形式,但出于篇幅考虑证明省略
    xxxyh
        33
    xxxyh  
       2021-02-19 11:33:10 +08:00
    函数的递归调用就是该函数在栈中有多个栈帧,程序只要模拟栈帧,不就可以将递归转化为迭代吗
    krixaar
        34
    krixaar  
       2021-02-19 11:45:01 +08:00
    这么说吧,如果让你手算一个递归过程,你怎么算?你先得按逻辑找“最底层”那一步,这样你才能算出个初始值往里面代,然后把结果代入这个算法再算,直到算出最终结果,而算的这个过程不就是迭代么……
    julyclyde
        35
    julyclyde  
       2021-02-19 11:53:26 +08:00
    把“判断是否再来一遍”和“再来一遍之前的准备和之后的收尾”放在里面就是递归,放在外面就是迭代
    leimao
        36
    leimao  
       2021-02-19 12:05:03 +08:00   ❤️ 1
    我觉得吧,V2EX 这个网站很多人回帖逼格弄的太高,高端喷子太多,很多人受不了都被劝退了。
    leimao
        37
    leimao  
       2021-02-19 12:07:37 +08:00
    即便问的问题在有些人看来有些幼稚,但是大家起点背景和水平都各不相同,没啥好喷的。
    lepig
        38
    lepig  
       2021-02-19 12:15:08 +08:00
    看了楼上的几位大神回复,我发现我这个高中生不配来发帖子和大家交流。 不再同一水平线上。
    msaionyc
        39
    msaionyc  
       2021-02-19 12:24:14 +08:00 via Android   ❤️ 1
    @hxndg 不要这样,我觉得你可以选择更友善的沟通方式。
    如果你真的觉得楼主这个帖子很傻不必发出来,你可以不点进来,没必要采取这种方式,一直问楼主为什么要发帖,是不是现在互联网已经不能接受重复的提问了
    另外,不是所有人的认知水平和经历,能力都和你一样,楼主来发帖讨论问题我不认为真的值得你如此对待
    ToBeHacker
        40
    ToBeHacker  
       2021-02-19 12:26:21 +08:00
    函数调用就是在压栈啊,只要你用一个显式的栈将参数存起来就可以了
    leimao
        41
    leimao  
       2021-02-19 12:31:18 +08:00
    @msaionyc 所以我现在只发娱乐休闲帖了 XD
    msaionyc
        42
    msaionyc  
       2021-02-19 13:10:44 +08:00
    @leimao 说难听一点,我觉得部分人有点清高得过分了
    mmdsun
        43
    mmdsun  
       2021-02-19 13:22:14 +08:00 via Android
    递归把计算交给计算机,归纳把计算交给人,前者是拿计算机的计算成本换人的时间,后者是拿人的时间换计算机的计算成本。

    用迭代和递归都能解决问题,但是使用递归时,由于有数学归纳法保证递归关系的正确性,所以只要专注于解决 2 个相邻层的关系就可以了,然后使用数学归纳法的基本情况作为递归出口。当然,在实际编程中,递归会增加函数调用栈的开销,也是要考虑的一方面
    lizytalk
        44
    lizytalk  
       2021-02-19 13:40:38 +08:00
    最直接的就是手动实现 stack 呗
    onec
        45
    onec  
       2021-02-19 17:47:41 +08:00
    肯定可以的,只是很多递归改起来太费脑子了
    stevefan1999
        46
    stevefan1999  
       2021-02-19 19:03:33 +08:00   ❤️ 1
    不能
    只有 totally computable 和 primitive recursive function 才可以
    是 totally computable 但不是 primitive recursive 的例子有 Ackermann function

    樓主你是沒有讀過 CS 嗎
    stevefan1999
        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))
    aptupdate
        48
    aptupdate  
       2021-02-19 19:15:08 +08:00 via iPhone
    Java 是的,而且大部分情况下转换为迭代后效率更高。
    yuelang85
        49
    yuelang85  
       2021-02-19 21:49:07 +08:00
    迭代就有为了优化递归而来的
    aec4d
        50
    aec4d  
       2021-02-19 22:18:37 +08:00   ❤️ 1
    这篇总结感觉写的很好 https://www.v2ex.com/t/675945
    chendl111
        51
    chendl111  
       2021-02-19 23:21:53 +08:00
    @hxndg 每当你想要批评别人时,你要记住,这个世界上所有的人,并不是个个都有过你拥有的那些优越条件——了不起的盖茨比
    no1xsyzy
        52
    no1xsyzy  
       2021-02-20 02:00:18 +08:00
    @stevefan1999 我觉得你理解错了迭代的意思……
    并不一定是能事先确定循环次数才叫迭代,牛顿迭代法甚至可能不停机。有名的几个分形集都是由“迭代产生的数列是否收敛”来定义的。
    dd112389
        53
    dd112389  
       2021-02-20 02:05:48 +08:00
    理论上所有递归都能转换为迭代实现, 并且迭代实现效率应该会比递归高.
    (抬杠说经过 xxxx 优化最后都是迭代的大可不必)
    msg7086
        54
    msg7086  
       2021-02-20 03:38:32 +08:00
    递归在操作系统层面上就迭代。递归的时候操作系统帮你把局部变量现场保存到栈里,然后帮你跳转到程序的头部继续执行。你想要数学证明,但其实递归就是迭代的一种实现。
    hxndg
        55
    hxndg  
       2021-02-20 09:30:44 +08:00 via Android
    @chendl111
    @msaionyc
    @msaionyc
    @lepig
    就连引用名人名言的都出来了……所以就连百度一下都成为了很高的门槛呗,呵呵,你们的友善真普世啊。

    lz 的问题非常精确,不是开放式问题,不需要任何开放式的回答。他原先的问题就有这种查查资料就能明白的问题,那他进步了吗?你们的友善除了让人舒服真的能起作用吗?

    普世价值观在工程和学术上没用
    akatquas
        56
    akatquas  
       2021-02-20 09:54:47 +08:00
    楼主对赌 10 w 的事情有下文吗?在线等
    akatquas
        57
    akatquas  
       2021-02-20 09:55:51 +08:00
    看错了,楼里面对赌 10 w 的事情。
    sakura1
        58
    sakura1  
       2021-02-20 10:40:01 +08:00
    当然可以
    hejw19970413
        59
    hejw19970413  
       2021-02-20 11:40:51 +08:00
    其实递归就是遍历的一种,只不过在这个过程中,不需要你来进行维护上一次的执行结果。递归也有好的递归和不好的递归,递归如果用不好的话,那么是非常容易出现问题的。
    heyhumor
        60
    heyhumor  
       2021-02-20 14:28:51 +08:00
    @hxndg 好牛逼,舌战群雄
    zxCoder
        61
    zxCoder  
       2021-02-20 14:59:18 +08:00
    可以
    canwushuang
        62
    canwushuang  
       2021-02-21 18:19:41 +08:00 via Android
    反之不行,递归在很多编译器有层数限制。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2559 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 34ms · UTC 01:36 · PVG 09:36 · LAX 17:36 · JFK 20:36
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.