递归函数的危险

问题内容：

经常有人说不建议在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:]

之后，我将其转换为非递归版本（我是python新手）

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有什么问题？

问题答案：

递归在Python中是“不好的”，因为它通常比迭代解决方案要慢，并且因为Python的堆栈深度不是无限的（并且没有尾调用优化）。对于求和函数，是的，您可能想要无限的深度，因为要对一百万个数字进行求和是完全合理的，而性能差异将成为包含大量项的问题。在这种情况下，您不应使用递归。

另一方面，如果要遍历从XML文件读取的DOM树，则不可能超过Python的递归深度（默认为1000）。当然 可以，
但是实际上不行。当您知道要使用哪种数据时，您可以确信不会溢出堆栈。

在我看来，递归树遍历比迭代遍历更自然地进行写入和读取，并且递归开销通常只占运行时间的一小部分。如果对您来说真正重要的是，它花费了16秒而不是14秒，那么扔PyPy可能是您更好地利用时间的方法。

递归似乎很自然地适合您所发布的问题，如果您认为代码更易于阅读和维护，并且性能足够，那么就去做吧。

我从小在计算机上编写代码，实际上，将递归深度限制为大约16（如果有的话），所以对我来说1000似乎很豪华。:-)

递归函数的危险

微信关注