递归函数的危险性

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

然后我把它改成了一个非递归的版本（我还是个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有什么问题吗？

Answer 1

你的时间测量完全不对：

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

def perms2(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

s = "01235678"
import itertools
perms3 = itertools.permutations

现在用 timeit 来测试一下：

thc:~$ for i in 1 2 3; do echo "perms$i:"; python -m timeit -s "import permtest as p" "list(p.perms$i(p.s))"; done 
perms1:
10 loops, best of 3: 23.9 msec per loop
perms2:
10 loops, best of 3: 39.1 msec per loop
perms3:
100 loops, best of 3: 5.64 msec per loop

你可以看到，itertools.permutations 速度是最快的，其次是递归版本。

但是那两个纯 Python 的函数根本没有机会快，因为它们做了一些很耗时的操作，比如像这样添加列表：perm[:i] + str[0:1] + perm[i:]

Answer 2

递归对于那些适合用简单明了的递归方式解决的问题来说是非常好的。但是，就像所有编程一样，你需要对算法进行一些分析，以了解它的性能特点。对于递归来说，除了要考虑操作的数量外，还必须估算最大栈深度。

很多问题出现在新手程序员身上，他们往往认为递归是神奇的，没意识到底下其实有一个栈在支撑着这一切。新手程序员也常常会分配内存却不释放，还有其他一些错误，所以递归并不是唯一存在这种风险的地方。

Answer 3

递归在Python中被认为是“坏”的，因为它通常比循环的方式要慢，而且Python的调用栈深度是有限的（而且没有尾调用优化）。以求和函数为例，如果你要对一百万个数字求和，确实希望有无限的深度，因为处理这么多数据时，性能差异会变得很明显。在这种情况下，你应该避免使用递归。

但如果你是在处理从XML文件读取的DOM树，通常不会超过Python的递归深度（默认是1000）。当然，有可能会超出，但实际上一般不会。当你提前知道自己要处理的数据类型时，可以放心不会导致栈溢出。

我认为，递归遍历树的写法和阅读起来都比循环方式更自然，而且递归带来的额外开销通常只是运行时间的一小部分。如果你真的在意的是运行时间从16秒变成14秒，使用PyPy可能会更值得你花时间。

递归似乎非常适合你提到的问题，如果你觉得这样写的代码更容易阅读和维护，而且性能也足够好，那就大胆去做吧。

我在编写代码的时候，曾经的计算机实际上将递归深度限制在大约16，如果根本有递归的话，所以1000的限制对我来说感觉很奢侈。:-)