请教有关 python 递归的问题

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

ans

list

ngetmprint

11 条回复 • 2016-09-08 17:14:51 +08:00

crayygy

2016-09-06 17:48:55 +08:00

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

billlee

2016-09-06 22:25:41 +08:00

把自己当成 python 执行一遍

thekoc

2016-09-07 09:06:13 +08:00

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

原理一样的

guyskk

2016-09-07 11:39:40 +08:00 via Android

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

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

2016-09-08 00:07:19 +08:00

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

popstk

2016-09-08 11:17:43 +08:00

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

2016-09-08 12:33:57 +08:00

@popstk really thx

slysly759

2016-09-08 12:34:33 +08:00

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

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

2016-09-08 17:14:51 +08:00

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