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
JCZ2MkKb5S8ZX9pq
V2EX  ›  Python

关于递归和 While

  •  
  •   JCZ2MkKb5S8ZX9pq · 2019-09-27 14:47:02 +08:00 · 4585 次点击
    这是一个创建于 1883 天前的主题,其中的信息可能已经有所发展或是发生改变。
    • 说实话直到最近,有时候写递归脑子还是会卡住。
    • 然后昨天顺手就把一个可以用递归表达的函数,直接写成了 while,好像也运行顺利。
    • 我就在想,是否 while 可以替代递归,把递归每次返回的值赋给变量。
    • 下面举两个简短的例子。
    def fact(n):
        if n == 1:
            print('fact: 1 = 1')
            return 1
        print(f'fact: {n} = {n}*fact({n-1})')
        return n * fact(n - 1)
    
    
    print(fact(10))
    
    • 在递归时,运行顺序是从外到内从,有点反过来的。
    def fact2(n):
        r = a = 1
        while True:  # 退出条件写在下面感觉更易读一点
            r *= a
            print(f'a={a} | r={r}')
            a += 1
            if a > n:
                return r
    
    
    print(fact2(10))
    
    • 用 while 写起来和理解起来都比较顺一点。

    • 我是美术半路出家的,现在就有点疑惑。
    • 想请教下各位高手,哪些情况下不适用 while 必须递归。
    • 或者递归有啥特别的优势嘛?
    18 条回复    2019-09-28 11:13:44 +08:00
    ipwx
        1
    ipwx  
       2019-09-27 15:10:08 +08:00   ❤️ 3
    1、只有尾递归才能比较容易地被转化为循环。并且,一个合格的程序员在这种情况下优先使用循环,除非你在用一些正统的函数式编程语言。
    2、非尾递归不太容易转换成循环。不过在写算法的时候,很多时候为了效率,也会想办法转化成循环。不过这需要借助额外的数据结构,比如队列或者栈。
    3、在 2 的情况下,递归远比非递归容易写、容易读。
    ipwx
        2
    ipwx  
       2019-09-27 15:15:07 +08:00
    顺便楼主你这情况就是尾递归。而且为啥要用 while,用 for 不就行了。

    http://ideone.com/3zaTEJ
    idealhs
        3
    idealhs  
       2019-09-27 15:26:04 +08:00
    代码是写给人看的,只是恰巧能够运行
    newtype0092
        4
    newtype0092  
       2019-09-27 15:28:27 +08:00
    递归转化成循环是一种普遍的优化方式吧
    reself
        5
    reself  
       2019-09-27 15:34:34 +08:00
    递归和递推公式容易转换。递归更"数学",循环更偏向"程序"
    JCZ2MkKb5S8ZX9pq
        6
    JCZ2MkKb5S8ZX9pq  
    OP
       2019-09-27 15:37:01 +08:00
    @ipwx 请问有没有情况 2 的合适的例子?
    reself
        7
    reself  
       2019-09-27 15:43:56 +08:00
    递归偏向于"是什么",就像数学归纳法中的初始条件和推理。你给的递归的例子里,代码本身就描述了阶乘的定义:f(n)=n*f(n-1)
    循环偏向于"怎么做",描述的实现方式而不是定义
    taogen
        8
    taogen  
       2019-09-27 15:49:06 +08:00 via Android
    递归使代码更简洁,但会消耗额外的内存。数据集合 size 比较大时,不适合用递归,容易发生 Stack overflow。
    Vegetable
        9
    Vegetable  
       2019-09-27 15:52:07 +08:00
    函数本身就是调用栈,所以,没有必须递归的算法。
    递归的优势是让算法更好理解。
    reself
        10
    reself  
       2019-09-27 15:52:11 +08:00
    @JCZ2MkKb5S8ZX9pq 因为函数调用其实就是局部环境的入栈和出栈,因此理论上所有递归都能转成循环,只是有的需要用栈来辅助(尾递归是特殊情况)。需要用栈辅助的情况下,其实不如递归易读。不过操作系统一般会限制函数调用栈的大小,所以不能保证调用深度的情况下,转成循环可以规避掉这个限制,也是有意义的。
    像树和图的场景,用递归就更简洁。
    wysnylc
        11
    wysnylc  
       2019-09-27 15:58:00 +08:00
    建议使用迭代代替所有递归,递归会导致栈溢出和逻辑不易读
    ipwx
        12
    ipwx  
       2019-09-27 16:33:59 +08:00
    @JCZ2MkKb5S8ZX9pq 例子很容易找,而且是标准算法。

    用栈辅助:图搜索的深度优先遍历。
    用队列辅助:图搜索的广度优先遍历。
    HolmLoh
        13
    HolmLoh  
       2019-09-27 16:58:11 +08:00
    @idealhs
    这是理想情况,正常情况是 代码要能运行,只是恰巧给人看的
    Amit
        14
    Amit  
       2019-09-27 17:20:51 +08:00
    我感觉递归更符合直觉,更容易理解。把递归改成循环,需要自己维护栈
    jmc891205
        15
    jmc891205  
       2019-09-27 17:41:22 +08:00
    主题叫“关于递归和迭代”更好一点
    因为实现迭代的方式有很多种 用 while 只是其中一种
    msg7086
        16
    msg7086  
       2019-09-28 04:29:06 +08:00
    迭代是一种递归的做法。当然有些递归不是那么容易写成循环就是了。
    不过说白了,循环和递归都是让当前运行指令跳回头部,所以本质上都是一样的,无非是要保存和恢复调用者的环境而已。循环就是一种(可能经过简化的)递归。
    luckyuro
        17
    luckyuro  
       2019-09-28 11:12:36 +08:00 via iPhone
    你的 1 改一下就是尾递归了,有很多语言对尾递归有优化。
    个人觉得递归和循环是思考 /看待问题角度的事情,个人认为有些问题拿递归来思考比较容易。
    还有就是,有些语言变量的值不能修改,这种情况下感觉循环会有些变扭,就会用递归
    luckyuro
        18
    luckyuro  
       2019-09-28 11:13:44 +08:00 via iPhone
    你永远可以用一个栈把递归转换成循环。关于尾递归的介绍可以看看 sicp 一开始的一章
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2781 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 13:06 · PVG 21:06 · LAX 05:06 · JFK 08:06
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.