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

现如今,递归的效率到底有多差

  •  
  •   snailsir · 2015-09-15 20:18:03 +08:00 · 5160 次点击
    这是一个创建于 3343 天前的主题,其中的信息可能已经有所发展或是发生改变。

    时常会遇到一些人在我说出递归时反驳说,递归的效率很差。好像还记得大学学 C 语言时,谭浩强也这么写过,老师也这样教我们。

    但,我在接触 lisp 之后,却发现处处都有递归的思想及应用,也没发现有什么差的地方,反倒是处理问题简单许多。

    所以始终不明白递归的效率到底有多差。一点猜测是,那个时候,计算机很奢侈;但现如今,随便一台电脑,性能都很好啊。

    12 条回复    2015-09-16 10:26:22 +08:00
    ruandao
        1
    ruandao  
       2015-09-15 20:44:35 +08:00
    你那个是迭代,只是用递归的形式显示
    snailsir
        2
    snailsir  
    OP
       2015-09-15 20:47:56 +08:00 via iPhone
    @ruandao
    ch3n2k
        3
    ch3n2k  
       2015-09-15 20:48:56 +08:00
    尾递归可以用,在支持尾递归优化的语言里面
    monsoon
        4
    monsoon  
       2015-09-15 20:48:56 +08:00
    有种递归叫尾递归。
    mthli
        5
    mthli  
       2015-09-15 20:52:19 +08:00 via Android
    是的,有种递归叫尾递归。
    caixiexin
        6
    caixiexin  
       2015-09-15 20:54:09 +08:00
    不是效率差,而是递归会导致内存溢出,尾递归除外- -
    ruandao
        7
    ruandao  
       2015-09-15 21:24:38 +08:00   ❤️ 1
    YuJianrong
        8
    YuJianrong  
       2015-09-15 21:46:38 +08:00   ❤️ 1
    1. 递归性能是真的差, call 一个函数的时候大多数语言都需要有一定程度的资源分配、释放等操作,这当然要比单纯循环性能更差。
    2. 为了能回溯,递归函数的参数和地址需要分配在 call stack 上,大部分语言的 call stack 大小都是有限的,递归太深就会爆掉
    3. 没有 side effect 的语言(如 lisp, haskell )当递归在尾部的时候可以做尾递归优化,这时函数其实并没有递归而被优化成循环了(实际上 lisp 没有循环本来做循环就得靠尾递归)。

    顺便黑一下 lisp ,这玩意玩玩就好其实根本不能适应现代大规模开发,我看还是学好 C++/java/JS 比较实在。
    ryd994
        9
    ryd994  
       2015-09-15 21:58:45 +08:00
    处理问题简单和性能好有什么关系?
    有尾递归优化时,开销相对较小,但也无非就是循环而已,考虑到初始化之类的成本,还是不如循环。
    没尾递归你就等着深度大的时候爆栈吧
    其实递归就是利用函数调用的机制做循环而已
    pynix
        10
    pynix  
       2015-09-15 23:27:05 +08:00
    优化。。。。
    snailsir
        11
    snailsir  
    OP
       2015-09-16 09:50:47 +08:00
    看到大家的回答,总结一下问题所在吧:

    1. 说开销,感觉还是在 函数调用堆栈 上面,这个各语言是的限制又不一样。
    2. 尾递归的话,得需要语言的支持。

    但感觉以上两点,也并没有限制 递归的扩张啊。就像当年的 goto 语句一样( linux 内核源码风格中提到了在什么情况下比较适合使用 goto )

    @ruandao 的例子然我想起了 lisp 里的做法貌似大都这样的,试了一下 php 版本的,居然也可以。



    @ryd994
    @YuJianrong
    ryd994
        12
    ryd994  
       2015-09-16 10:26:22 +08:00 via Android
    @snailsir 限制再不一样,优化的再好,还是有,而且不会小。递归真心只有设计算法的时候感觉好。实现的时候就是大坑。出错的时候 debug 也更麻烦。 lisp 本来就是理论性很强的语言,感觉好不奇怪。 C 里面爆栈太容易。你确定递归用的很多?确实有递归好用的情况,但大多数情况都不是这样。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2697 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 324ms · UTC 06:44 · PVG 14:44 · LAX 22:44 · JFK 01:44
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.