The danger of recursive functions

Question

Often people say that it is not recommended to use recursive functions in python (restrictions on the depth of recursion, memory consumption, etc.)

I took an example of permutation from this question .

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

Subsequently, I converted it to a non-recursive version (I'm new to 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 

And I compared them

 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) 

The results are quite interesting. A recursive function is the fastest of 5 seconds, then non-recursive 8 seconds, and then building 35 seconds.

So recursive functions, what's bad in Python? What is wrong with itertools.permutations built-in?

Answer 1

Recursion is "bad" in Python because it is usually slower than an iterative solution, and because the depth of the Python stack is not unlimited (and there is no tail call optimization). For the sum function, yes, you probably want unlimited depth, since it would be wise to want to summarize a list of a million numbers, and the performance delta would become a problem with so many elements. In this case, you should not use recursion.

If you walk through the DOM tree readable from an XML file, on the other hand, you are unlikely to exceed the Python recursion depth (default is 1000). This, of course, could, but, in fact, it probably would not. When you know what data you will work ahead of time, you can be sure that you will not overflow the stack.

Recursive tree-like movement, in my opinion, is much more natural to write and read than iterative, and recursion overheads, as a rule, make up a small part of the execution time. If it really matters to you that instead of 14 it takes 16 seconds to throw PyPy , it might be better to use your time.

Recursion seems like natural adaptability to the problem you posted, and if you think the code is easier to read and maintain in this way and the performance is adequate, then look for it.

I grew up writing code on computers that, for practical reasons, limited the recursion depth to about 16, if it was provided at all, so 1000 seems luxurious to me. :-)

Answer 2

Recursion is good for problems that lend themselves to clean, clear, recursive implementations. But, like all programs, you must perform some analysis algorithm to understand the performance characteristics. In the case of recursion, in addition to the number of operations, you should also evaluate the maximum stack depth.

Most problems arise when new programmers assume that recursion is magical and do not realize that there is a stack under it. It is known that new programmers allocate memory and never free it and other errors, so recursion is not unique in this danger.

Answer 3

Your timings are completely wrong:

 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 

Now test it with timeit:

 thc:~$ for i in 1 2 3; do echo "perms$i:"; python -m timeit -s "import permtest as p" "list(p.perms$i(ps))"; 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 

As you can see, itertools.permutations is by far the fastest, followed by a recursive version.

But even a pure Python function did not have a chance to be fast, because they perform expensive operations, such as adding lists ala perm[:i] + str[0:1] + perm[i:]

Answer 4

I can not reproduce the synchronization results (in Python 2.6.1 on Mac OS X):

 >>> import itertools, timeit >>> timeit.timeit('list(all_perms("0123456789"))', ... setup='from __main__ import all_perms'), ... number=1) 2.603626012802124 >>> timeit.timeit('list(itertools.permutations("0123456789"))', number=1) 1.6111600399017334