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

请教有关 python 递归的问题

  •  
  •   slysly759 · 2016-09-06 17:41:11 +08:00 · 2795 次点击
    这是一个创建于 3018 天前的主题,其中的信息可能已经有所发展或是发生改变。

    需求如下: 输入一段 list 长度为 M ,和需要随机提取的 list 长度为 N ,返回所有可能的 list 例如输入[1,2,3,4,5,6,7] 3 那么第一个需要返回的自然是[1,2,3] 我在 CSDN 上看到有人写了这样一段递归(原来是 print 我改成 return 了)

    special=[]
    def ngetmprint(list,ans,m):
        if m==len(list):
            ans = ans + list
            # print(ans)
            special.append(ans)
        elif m==0:
            # print(ans)
            special.append(ans)
        else:
            ngetmprint(list[1:],ans+list[0:1],m-1)
            ngetmprint(list[1:],ans,m)
        return special
    
    

    当我想弄清楚他的原理时候,发现在生成完比如[1,2,]后 list 会慢慢自增加到 [ 4,5,6,7 ] 然后再递归那个[1,,3] 对了他那个函数的 ans 填一个空的 list 比如[]就好 有好心人可以帮我讲讲这是怎么回事喵~ PS:至于网上那些尾递归或者罗汉塔循环乘数什么的就不用提了,如果有好的当然不吝赐教~

    11 条回复    2016-09-08 17:14:51 +08:00
    crayygy
        1
    crayygy  
       2016-09-06 17:48:55 +08:00
    最直接的方法是自己打几个断点跟下去
    billlee
        2
    billlee  
       2016-09-06 22:25:41 +08:00
    把自己当成 python 执行一遍
    thekoc
        3
    thekoc  
       2016-09-07 09:06:13 +08:00
    guyskk
        4
    guyskk  
       2016-09-07 11:39:40 +08:00 via Android
    首先,这个函数的作用是取 ans 中所有的元素+list 中取 m 个元素,然后把 list 中取 m 个元素这个步骤分解为:
    这 m 个元素中包含 list 的第一个元素和不包含 list 的第一个元素,把大问题分解为两个小问题递归求解。
    aec4d
        5
    aec4d  
       2016-09-07 23:30:42 +08:00
    @crayygy 的说法是非常误导人的,对于递归算法打断点跟踪栈调用是相当不明智的,因为几行的递归代码会造成非常非常多的函数调用,从数学逻辑上理解递归才是明智的。
    上面写的是一个组合算法, python 有自带模块 from itertools import combinations,题主给的代码大意是等同于①取出第一个元素然后算 m-1 的组合,结果加上第一个元素 ②取出第一个元素,算 m 的组合
    这个过程在满足递归结束条件的时候把结果加入到 special 列表,属于有去无回,这个过程的 2 步是可以调换位置的,所以代码中调换也不会影响结果
    再用另外一种思虑
    取出 m 个元素等同于,移除某一个元素,然后算 m 的组合(每个元素都移出一次,排除重复项)
    https://gist.github.com/anonymous/517607265f6c60cd4d0a94d76018460f

    附 2 个觉得写得比较好的递归博文
    http://zisong.me/post/suan-fa/ren-nao-li-jie-di-gui
    http://www.nowamagic.net/librarys/veda/detail/2314
    stillwater
        6
    stillwater  
       2016-09-08 00:07:19 +08:00
    从 list 中取 m 个元素的所有组合 = 除 list 第一个元素外取 m-1 个元素的所有组合 + 除 list 第一个元素外取 m 个元素的所有组合
    popstk
        7
    popstk  
       2016-09-08 11:17:43 +08:00   ❤️ 1
    组合问题,根据组合公式 C(m,n)=C(m-1,n-1)+C(m, n-1)
    ngetmprint(list,ans,m): #C(m,n) len(list)=n , ans 是保存上次递归已有的元素,第一次调用当然是空的
    ngetmprint(list[1:],ans+list[0:1],m-1) #C(m-1,n-1) 这里取 n 的第 1 个即 list[0:1],仍需从剩下的 list[1:]取 m-1 个
    ngetmprint(list[1:],ans,m) #C(m, n-1) 从剩下的 list[1:]取 m 个

    要是罗汉塔真的理解了,有了公式相信不难写出
    另外跟一下 ans 每次保存的状态,也能帮助理解公式的意义
    slysly759
        8
    slysly759  
    OP
       2016-09-08 12:33:57 +08:00
    @popstk really thx
    slysly759
        9
    slysly759  
    OP
       2016-09-08 12:34:33 +08:00
    @aec4d 感谢,等这几天感冒好了就来看~
    ecloud
        10
    ecloud  
       2016-09-08 16:57:34 +08:00
    python 怎么说呢,我的经验是慎用递归
    我曾经有过这么一段代码
    def getMobilePair(smobile):
    tmobile = getMobile("")
    if tmobile == smobile:
    getMobilePair(smobile)
    else:
    return tmobile

    其中的 getMobile("")是从一个池中随机取出一个手机号,然后这个递归得到另外一个不相同的随机的手机号
    具体的情形我已经有点淡忘了,大概情况是当程序以多线程运行每秒上千次请求(这个递归相关的大约占 5%)的时候, python 递归执行的速度跟不上整体逻辑,出现了一些意想不到的结果
    后来我只能把一个号码池分割成两部分,烦别取随机,就再没有出过毛病
    slysly759
        11
    slysly759  
    OP
       2016-09-08 17:14:51 +08:00
    @ecloud 我明白 但是对于小需求 想写小而美的代码 理解递归简直太棒了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5073 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 33ms · UTC 07:48 · PVG 15:48 · LAX 23:48 · JFK 02:48
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.