递归函数的危险

Question

通常有人说不建议在python中使用递归函数(递归深度限制,内存消耗等)

我从这个问题中得到了一个排列的例子.

def all_perms(str):
  if len(str) <=1:
    yield str
  else:
    for perm in all_perms(str[1:]):
        for i in range(len(perm)+1):
            yield perm[:i] + str[0:1] + perm[i:]

后来我把它变成了一个不递归的版本(我是一个蟒蛇新手)

def not_recursive(string):
  perm = [string[0]]
  for e in string[1:]:
    perm_next = []
    for p in perm:
        perm_next.extend(p[:i] + e + p[i:] for i in range(len(p) + 1))
    perm = perm_next

  for p in perm:
    yield p

我比较了他们

before=time()
print len([p for p in all_perms("1234567890")])
print "time of all_perms %i " % (time()-before)

before=time()
print len([p for p in not_recursive("1234567890")])
print "time of not_recursive %i " % (time()-before)

before=time()
print len([p for p in itertools.permutations("1234567890")])
print "time of itertools.permutations %i " % (time()-before)

结果非常有趣.递归函数是最快的一个5秒,然后不递归8秒,然后建立35秒.

那些在Python 中不好的递归函数呢？内置的itertools.permutations有什么问题？

Answer 1

递归是好的对于借给自己干净,清晰,递归的实现问题.但与所有编程一样,您必须执行一些算法分析才能理解性能特征.在递归的情况下,除了操作次数之外,还必须估计最大堆栈深度.

当新程序员认为递归是神奇的并且没有意识到底层有一个堆栈使得它成为可能时,大多数问题都会发生.新的程序员也已经知道分配内存并且永远不会释放它,以及其他错误,因此递归在这种危险中并不是唯一的.

Answer 2

递归在Python中是"坏的",因为它通常比迭代解决方案慢,并且因为Python的堆栈深度不是无限的(并且没有尾调用优化).对于求和函数,是的,您可能想要无限深度,因为想要对一百万个数字的列表求和是完全合理的,并且性能增量将成为如此大量项目的问题.在这种情况下,您不应该使用递归.

另一方面,如果您正在从XML文件读取DOM树,则不太可能超过Python的递归深度(默认为1000).它当然可以,但作为一个实际问题,它可能不会.当您知道将要使用哪种类型的数据时,您可以确信不会溢出堆栈.

在我看来,递归树行走比写入和读取更自然,并且递归开销通常是运行时间的一小部分.如果对你来说真的很重要,它需要16秒而不是14秒,扔掉PyPy可能会更好地利用你的时间.

递归似乎很适合你发布的问题,如果你认为代码更容易阅读和维护,并且性能足够,那就去吧.

我从小就在计算机上编写代码,作为一个实际问题,有限的递归深度大约为16,如果提供的话,那么1000对我来说似乎很奢侈.:-)