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

计算机界为什么推崇递归思维?

  •  
  •   africwildman · 2019-06-12 08:10:47 +08:00 · 7900 次点击
    这是一个创建于 1751 天前的主题,其中的信息可能已经有所发展或是发生改变。

    各种算法书都会夸一夸递归之美,但递归性能差,容易爆栈,唯一的好处就是人的智商理解起来容易一点,写出来的代码看着更甜(所谓优雅)。我没感觉递归有多好,不如循环,不值得推崇。

    46 条回复    2019-06-12 20:11:26 +08:00
    momocraft
        1
    momocraft  
       2019-06-12 08:13:28 +08:00
    數學歸納法是基礎之一, 不過計算能力上只和循環等價的
    javlib
        2
    javlib  
       2019-06-12 08:15:52 +08:00 via Android
    尾递归可以转化为迭代,而且递归更容易表达“人“的思路。
    africwildman
        3
    africwildman  
    OP
       2019-06-12 08:17:00 +08:00
    @javlib 尾递归是循环的包装。
    Akiyu
        4
    Akiyu  
       2019-06-12 08:27:00 +08:00   ❤️ 1
    也算不上推崇吧
    递归就是一种思维方式, 一种规律
    当面临一些难以追踪和管理的数据结构时, 例如俄罗斯套娃一样的问题, 递归尤其重要
    使用递归处理这些问题, 你只需要观察得出局部的规律, 然后以递归形式写出来, 难度和代码简洁程序都大有裨益

    至于不如循环, 这个看你自己了. 循环的话, 所有的数据管理都得自己来做
    比如汉诺塔, 在未得出封闭解的情况下. 用循环来实现, 那想想就头疼...
    PALELESS
        5
    PALELESS  
       2019-06-12 08:31:54 +08:00
    没必要纠结什么包装什么, 如果因为尾递归是循环的包装就直接写循环, 那么为什么不去写机器码而是用高级语言? 都是为了便于理解?
    dugive
        6
    dugive  
       2019-06-12 08:37:15 +08:00 via Android
    马克
    africwildman
        7
    africwildman  
    OP
       2019-06-12 08:39:25 +08:00
    @Akiyu 看来是我写的少,没有这些感触。
    passerbytiny
        8
    passerbytiny  
       2019-06-12 08:40:43 +08:00   ❤️ 1
    你自己都已经把原因说出来了——人的智商理解起来容易一点。虽然你看不起人的智商,但是你改变不了可读性比性能重要的事实。另外,递归对应的是数学上的迭代。
    secsilm
        9
    secsilm  
       2019-06-12 08:45:04 +08:00 via Android
    从哪看的说递归写法比较优雅的?
    1a0ma0
        10
    1a0ma0  
       2019-06-12 08:52:39 +08:00
    我就是单纯觉的有意思,你看看那个 lisp 的符号表达式就是递归的。
    chrisliu1314
        11
    chrisliu1314  
       2019-06-12 08:56:56 +08:00 via iPhone
    递归可以将一个问题分解为子问题,从而解决问题。性能的问题,可以通过加缓存,避免重复计算。
    q8164305
        12
    q8164305  
       2019-06-12 08:59:25 +08:00 via Android
    递归,更接近数学思维,数学归纳法,所以很优雅
    est
        13
    est  
       2019-06-12 09:09:08 +08:00
    这个问题不适宜直接回答。其实可问一个类似的问题:

    为什么物理界这么推崇对称?

    其实他们背后都是同一个答案。
    yushi17
        14
    yushi17  
       2019-06-12 09:13:45 +08:00 via Android
    能用循环不用递归。真的有书推崇写递归吗?可能只是用递归思想分析问题吧。能转化成循环的要转化
    heyjei
        15
    heyjei  
       2019-06-12 09:18:56 +08:00
    对于那种变量类型只有 val 没有 var 的编程语言来说,递归差不多是解决问题唯一的写法
    acehow
        16
    acehow  
       2019-06-12 09:22:21 +08:00 via Android
    啥叫不如循环,复杂度一样的啊,还更易读。
    VD
        17
    VD  
       2019-06-12 09:23:14 +08:00   ❤️ 1
    草稿用递归,优化时转循环
    FromNowToNow
        18
    FromNowToNow  
       2019-06-12 09:24:20 +08:00 via Android
    代码简短优雅、符合人的思维习惯。崇尚递归就像崇尚用动态规划一样,体现 coder 的思维和代码能力
    smallpython
        19
    smallpython  
       2019-06-12 09:29:19 +08:00
    我的理解是递归可以显得 coder 更牛逼
    zhila
        20
    zhila  
       2019-06-12 09:33:21 +08:00
    beautiful,各种意义上
    jmc891205
        21
    jmc891205  
       2019-06-12 09:35:56 +08:00 via iPhone
    担心爆栈就自己搞个栈 这不算啥大问题
    codecrash
        22
    codecrash  
       2019-06-12 09:53:26 +08:00 via Android
    美感
    ech0x
        23
    ech0x  
       2019-06-12 09:55:56 +08:00   ❤️ 1
    因为美,简洁的美,抽象的美。
    lambda 表达式依赖递归就可以构建出与图灵机等价的计算模型。
    曾经人们觉得一个编程语言里没有 goto 是无法写程序的,正如现在人们都觉得没有循环语句是没法写程序的,但 Dijkstra 证明了 Goto 对于程序语言来说不是必须的,也正如这世界上是有还「活着」的语言是没有循环语句的( Haskell 就是一个极好的例子)。
    所以说学一门函数式编程语言能让你的眼界开阔。
    testeststs
        24
    testeststs  
       2019-06-12 10:08:38 +08:00
    软件工程为什么先要系统设计,然后详细设计,然后编码和调试?
    编程的时候为什么先写接口,框架搭完了,然后再写详细实现?
    GjriFeu
        25
    GjriFeu  
       2019-06-12 10:08:45 +08:00 via iPhone
    代码是写给人看的
    annoymous
        26
    annoymous  
       2019-06-12 10:11:41 +08:00
    递归便于思考 或者说更容易发现规律与解法
    CSM
        27
    CSM  
       2019-06-12 10:23:22 +08:00 via Android
    递归处理树这些本身就递归的数据结构上有天然的优势,还有就是在函数式语言大量使用了。

    另外 @annoymous 你 ID 有 typo🐶
    limbo0
        28
    limbo0  
       2019-06-12 10:23:26 +08:00 via Android
    因为现代的计算机不是设计成函数式的
    annoymous
        29
    annoymous  
       2019-06-12 10:26:09 +08:00
    @CSM #27 正确的已经被人注册了
    runze
        30
    runze  
       2019-06-12 10:31:26 +08:00
    递归更符合数学思维,
    爆栈是语言的问题,
    递归和循环各自有最适合的场景,
    两者都能用的时候未必一定要用递归。
    congeec
        31
    congeec  
       2019-06-12 10:32:47 +08:00 via iPhone
    @secsilm Haskell 我用的不多,目前写起来很优雅。
    mcfog
        32
    mcfog  
       2019-06-12 10:41:58 +08:00 via Android
    这里陷阱在于推崇是个人对一个东西主观的认可和赞誉,“递归思维”即使 LZ 写成思维,也还是一个解决问题的方式方法,无法被推崇,或者说推崇方式方法本身并不是一种科学的思维方式

    我觉得“推崇”递归是不对的,但我也完全不赞同楼主的观点,原因如上
    southsala
        33
    southsala  
       2019-06-12 10:55:39 +08:00
    同意 22l 的观点,不管什么“思维”,都是针对某些问题的,没有银弹“思维”
    pkookp8
        34
    pkookp8  
       2019-06-12 11:07:20 +08:00 via Android
    1.简洁
    2.简洁
    3.简洁
    4.不要过早优化
    MoRun
        35
    MoRun  
       2019-06-12 11:36:37 +08:00
    爆栈是语言问题
    递归是思维方式
    递归可以写成迭代的形式
    很多函数式编程语言没有循环
    watzds
        36
    watzds  
       2019-06-12 12:01:46 +08:00 via Android
    递归只是个表达方式,谁真到处写递归啊?
    thedog
        37
    thedog  
       2019-06-12 12:11:59 +08:00
    用逻辑学的理论来说,自我复用是智能的基础之一。递归是自我复用的程序表达
    wdv2ly
        38
    wdv2ly  
       2019-06-12 12:20:16 +08:00
    你说的唯一的好处带来的价值已经远超过所谓的坏处降低的价值了,所以就应该推崇。
    GeruzoniAnsasu
        39
    GeruzoniAnsasu  
       2019-06-12 12:49:37 +08:00 via Android
    推荐文章:永恒的金色对角线
    http://mindhacks.cn/2006/10/15/cantor-godel-turing-an-eternal-golden-diagonal/

    递归不是思维方法和设计模式,递归是数学和集合论的通俗化。你站到了很多年前第一个可递归程序设计者对面——那些计算机专家和数学家的身旁。可以说已经达到了很高的境界。
    shadownet
        40
    shadownet  
       2019-06-12 13:16:00 +08:00
    你有更好的办法?
    ZRS
        41
    ZRS  
       2019-06-12 13:22:06 +08:00
    漂亮
    shiji
        42
    shiji  
       2019-06-12 13:29:36 +08:00 via Android
    递归性能不差。就是对智商
    shiji
        43
    shiji  
       2019-06-12 13:32:38 +08:00 via Android
    有一定的要求。。。

    尤其是计算机老师在教 prolog 的时候。。。
    vianEm
        44
    vianEm  
       2019-06-12 18:46:20 +08:00 via iPhone
    等接手过一个可读性差的项目,就知道可读性的重要性了
    mengcanzhai
        45
    mengcanzhai  
       2019-06-12 19:06:43 +08:00
    递归更抽象
    skydev
        46
    skydev  
       2019-06-12 20:11:26 +08:00
    看一下 GNU 的定义:GNU 是 GNU's Not Linux 的首字母缩写。
    你们看这个递归得如何?
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   998 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 31ms · UTC 19:53 · PVG 03:53 · LAX 12:53 · JFK 15:53
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.