请教有关 python 递归的问题

[slysly759]

需求如下： 输入一段 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:至于网上那些尾递归或者罗汉塔循环乘数什么的就不用提了，如果有好的当然不吝赐教~

[crayygy]

最直接的方法是自己打几个断点跟下去

[billlee]

把自己当成 python 执行一遍

[thekoc]

https://www.zhihu.com/question/21075235

原理一样的

[guyskk]

首先，这个函数的作用是取 ans 中所有的元素+list 中取 m 个元素，然后把 list 中取 m 个元素这个步骤分解为:
这 m 个元素中包含 list 的第一个元素和不包含 list 的第一个元素，把大问题分解为两个小问题递归求解。

[aec4d]

@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]

从 list 中取 m 个元素的所有组合 = 除 list 第一个元素外取 m-1 个元素的所有组合 + 除 list 第一个元素外取 m 个元素的所有组合

[popstk]

组合问题，根据组合公式 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]

@popstk really thx

[slysly759]

@aec4d 感谢，等这几天感冒好了就来看~

[ecloud]

python 怎么说呢，我的经验是慎用递归
我曾经有过这么一段代码
def getMobilePair(smobile):
tmobile = getMobile("")
if tmobile == smobile:
getMobilePair(smobile)
else:
return tmobile

其中的 getMobile("")是从一个池中随机取出一个手机号，然后这个递归得到另外一个不相同的随机的手机号
具体的情形我已经有点淡忘了，大概情况是当程序以多线程运行每秒上千次请求（这个递归相关的大约占 5%）的时候， python 递归执行的速度跟不上整体逻辑，出现了一些意想不到的结果
后来我只能把一个号码池分割成两部分，烦别取随机，就再没有出过毛病

[slysly759]

@ecloud 我明白 但是对于小需求 想写小而美的代码 理解递归简直太棒了