V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
Loop680
V2EX  ›  Python

对于内存占用来说,递归和循环中的哪个对资源的利用比较高效?

  •  
  •   Loop680 · 2014-12-02 09:21:14 +08:00 · 7191 次点击
    这是一个创建于 3663 天前的主题,其中的信息可能已经有所发展或是发生改变。
    请教一下前辈们,我刚开始学Python,看的是Python基础教程,第6.6章节里面提到了幂指数运算的例子:

    循环版本
    def power(x,n):
    result = 1
    for i in range(n):
    result *= x
    return result

    递归版本
    def power(x,n):
    if n = 0:
    return 1
    else:
    return x * power(x,n-1)

    在前面的讲解中用了无限递归导致内存崩溃超过最大递归深度的例子,那是不是就说递归这种每次都调用自身的行为更加消耗内存资源呢?
    32 条回复    2014-12-03 09:05:56 +08:00
    xpfd
        1
    xpfd  
       2014-12-02 09:32:34 +08:00   ❤️ 2
    python机理不懂,从c语言角度解释一下递归和循环的区别吧,递归相当于不停的调用自身函数,每调用一次都会在栈上申请一次,所以如果递归次数过多会导致栈溢出,就跟吃饭一样,不停的吃不停的吃,一直吃到最后全吐出来。
    而循环是每次申请一次栈,循环结束后函数返回会执行出栈操作,也就是说每次都是吃一口,吐出来,然后再吃一口吐出来,明白了吧
    est
        2
    est  
       2014-12-02 09:38:33 +08:00   ❤️ 1
    @Loop680 @xpfd 有个东西叫尾递归优化,实质就是把递归转换为循环。
    wy315700
        3
    wy315700  
       2014-12-02 09:40:03 +08:00   ❤️ 2
    图灵曾经证明过,一切递归都可以用一个等价循环来完成。
    Loop680
        4
    Loop680  
    OP
       2014-12-02 09:45:24 +08:00
    @xpfd 那即是说,递归的意义仅在于优雅?
    asassas
        5
    asassas  
       2014-12-02 09:47:41 +08:00   ❤️ 1
    是的,楼主可以google一下“Stack Frames”或者“栈帧”。
    一般语言中,每次函数调用都会在栈上保存返回地址,分配局部变量等。
    所以递归这种连续嵌套的函数调用就比较消耗内存,而循环不存在这些问题。
    好像具有尾递归优化的语言能够避免这种内存消耗吧,python目前貌似还不支持。
    jox
        6
    jox  
       2014-12-02 09:47:50 +08:00 via iPhone   ❤️ 1
    python不支持尾递归优化 循环只需要当前栈 递归会创建多个栈 但是循环的本质是递归 循环能处理的问题递归也能处理 递归能处理的问题循环只能处理一部分 使用python不需要考虑性能 尤其是新手 当性能成为问题的时候再考虑优化 绝大多数场合没有考虑递归与循环那个效率高的必要
    Loop680
        7
    Loop680  
    OP
       2014-12-02 09:49:16 +08:00
    @jox 明白了,精简易读的代码才是首要追求的目标吧。
    mengzhuo
        8
    mengzhuo  
       2014-12-02 09:52:35 +08:00   ❤️ 1
    CPython有个问题……就是递归不能超过99……╮(╯▽╰)╭

    在占用方面自然是循环完胜,因为不需要建立执行空间
    xpfd
        9
    xpfd  
       2014-12-02 09:56:11 +08:00   ❤️ 1
    @Loop680 我觉得主要是因为需要用递归的场景写起来逻辑比你转换成循环的要简单,跟优雅没什么关系,我认为代码在保证功能和性能的前提下,要尽量写的简单易懂,对于以后维护有很大的帮助
    xpfd
        10
    xpfd  
       2014-12-02 09:58:37 +08:00   ❤️ 1
    @est 又学到一招了:) 不过实际工作中能不用递归就尽量不用递归,递归用不好很容易出事
    abscon
        11
    abscon  
       2014-12-02 10:01:17 +08:00   ❤️ 1
    @wy315700
    那这个“等价的循环”是否需要手工维护一个堆栈?是的话并没有对资源的利用更高效。

    @Loop680
    困难的问题本质就是困难的,并不会由于换一种表达方式就变简单了。在需要维护历史记录时,不管循环还是递归对资源的利用都“不高效”。

    只有在能做尾递归优化而又未做时,才可以说循环效率优于递归。
    但不是什么情况都能做尾递归优化的。
    yueyoum
        12
    yueyoum  
       2014-12-02 10:01:39 +08:00   ❤️ 1
    用erlang吧, 递归既符合我个人的思维,代码也好写
    wy315700
        13
    wy315700  
       2014-12-02 10:05:56 +08:00   ❤️ 1
    @abscon 是算法层面的。不需要模拟一个栈
    withrock
        14
    withrock  
       2014-12-02 10:06:42 +08:00   ❤️ 1
    递归优美,自上而下;但循环更高效,自下而上。
    jox
        15
    jox  
       2014-12-02 10:22:18 +08:00 via iPhone   ❤️ 1
    在写程序的时候递归和循环在表达力上是等价的 可以互相转换 有些递归需要记录每次递归开始时的状态 如果使用循环可以借助创建用户栈来记录这些状态来模拟递归 这样在内存占用上循环没有太大优势 但是在缺少尾递归优化支持的时候依然会减少函数调用带来的支出 不需要记录状态的问题 在有尾递归优化的时候循环在效率上的优势是微乎其微的

    但是有些问题用递归解决很自然 比如树的遍历 比如需要divide and conquer策略的算法 有些问题用循环解决很自然 比如列表的遍历
    这样的时候选择最合适的手段解决问题是很自然的 让编译器去做优化工作就行了 但是因为大多数时候递归的程序都很简短和优雅 所以有些人会偏爱递归
    tftk
        16
    tftk  
       2014-12-02 10:25:02 +08:00   ❤️ 1
    递归是计算机的精髓所在。
    eriale
        17
    eriale  
       2014-12-02 10:27:49 +08:00
    python不支持尾递归,所以能用循环,尽量用循环,不到万不得已的时候,不要用递归。
    如果在产品开发中要用递归,最好也确认递归层数比较少。
    abscon
        18
    abscon  
       2014-12-02 10:31:39 +08:00
    @wy315700 换一种问法:把任意递归算法转换成循环时,算法的时间或者空间复杂度是否保持不变?或者必然降低?

    因为@Loop680 问的是“对资源的利用比较高效”。
    wy315700
        19
    wy315700  
       2014-12-02 10:40:05 +08:00 via Android
    @abscon 这就没研究过了,没有那么深的内功
    Loop680
        20
    Loop680  
    OP
       2014-12-02 10:48:21 +08:00
    @abscon 嗯对,我也想问关于算法的执行时间会不会有所提高。尽可能地追求效率嘛。
    znoodl
        21
    znoodl  
       2014-12-02 10:57:49 +08:00 via iPhone   ❤️ 1
    所有的递归都可转换成非递归,分为直接转换和间接转换,间接转换用栈模拟调用
    besto
        22
    besto  
       2014-12-02 10:59:18 +08:00   ❤️ 1
    楼上该说的都说了,补充几点:
    1. 递归确实可以用循环替代,但是尾递归优雅(不是好看的意思)。
    2. 尾递归程序不是那么容易写的,参考Lisp的程序,但尾递归的开销约等于循环。
    3. 非尾递归会引起栈崩,100,1000,1w,10w,100w来测试qsort,总有能蹦的时候
    4. Python类似的高级语言,考虑这种细节意义不是太大。
    Loop680
        23
    Loop680  
    OP
       2014-12-02 11:10:22 +08:00
    @besto 学到了很多意外的知识啊,好开心,多谢多谢
    besto
        24
    besto  
       2014-12-02 11:13:47 +08:00
    @Loop680 刚学习某种语言,纠结这个,不如继续学习点python特性。
    语言具有相同性,你这个问题,恰恰不是python独有的,C也有,Java也有(当然Lisp没有...)
    ====================================================================
    很多程序员最终的代码都是控制逻辑,而非算法逻辑。。。。
    Bluecoda
        25
    Bluecoda  
       2014-12-02 11:20:17 +08:00
    递归的好处是高级的抽象

    上面解释了很多,递归因为种种原因,达不到循环的性能。唯一能够达到循环的性能的,就是优化过的尾递归。
    Loop680
        26
    Loop680  
    OP
       2014-12-02 11:33:21 +08:00
    @besto 今天看书的时候偶尔想到的一点东西,不是特别明白就来问一下,没有纠结的。^_^
    yunshansimon
        27
    yunshansimon  
       2014-12-02 17:11:57 +08:00
    递归用在处理链表上,你如果不是链表结构的话,就不要用递归了。
    alsotang
        28
    alsotang  
       2014-12-02 17:29:13 +08:00
    循环和尾递归都内存友好,递归的话,不好判断
    kingcos
        29
    kingcos  
       2014-12-02 18:47:36 +08:00
    。。。你可以看中国MOOC大学的数据结构,浙大的,就讲这个了!!
    不过他举例的是C语言。。。我现在大概给你说说吧,不知道对不对呢~~~
    他举例:写程序实现一个函数PrintN,使得传入一个正整数为N的参数后,能顺序打印1到N的全部正整数。
    然后用递归,当n = 100,000时,递归就直接崩溃了,而循环的话,就没问题,你可以试下~
    他的说明:递归虽然可以让我们更加清晰的写出代码,但是计算机不愿意做递归:因为递归对空间的占用过于庞大,超过了他能占用的空间,程序没有打出一个数字就崩溃了。

    PS我也准备学python呢。。。刚学完C就学python会不会有些过快呢?
    @Loop680
    kingcos
        30
    kingcos  
       2014-12-02 18:49:50 +08:00
    忘了解释了= =
    for循环:空间占用永远是个常量,不会随着n的增长而增长对内存的占用。
    递归:当n越大时,S(n)呈线性增长,而这个函数所占空间是有限的,当把他的有限空间用完,程序就会崩溃。(S(n)是空间复杂度~:根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限,造成程序非正常中断。)
    327beckham
        31
    327beckham  
       2014-12-02 19:19:50 +08:00
    递归不太好,果断循环。
    1023400273
        32
    1023400273  
       2014-12-03 09:05:56 +08:00
    @xpfd 通俗易懂啊
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3800 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 33ms · UTC 05:26 · PVG 13:26 · LAX 21:26 · JFK 00:26
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.