danger of recursive functions

Question

Often people say that it's not recommended to use recursive functions in python (recursion depth restrictions, memory consumption, etc)

I took a permutation example 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:]

Afterwards I transformed it into a not recursive version (I'm a python newbie)

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. The recursive function is the fastest one 5 sec, then not recursive 8 sec, then buildin 35 sec.

So are recursive functions that bad in Python? What is wrong with build-in itertools.permutations ?

Can we assume you checked that the output of the three functions is identical? — robert, Nov 25 '10 at 14:56
At least the size is identical. I checked the full list for 3 elements they are identical — Oleg Pavliv, Nov 25 '10 at 14:58

kindall · Accepted Answer · 2018-02-14T16:54:09.807

Recursion is "bad" in Python because it is usually slower than an iterative solution, and because Python's stack depth is not unlimited (and there's no tail call optimization). For a sum function, yes, you probably want unlimited depth since it would be perfectly reasonable to want to sum a list of a million numbers, and the performance delta will become an issue with such a large number of items. In that case you should not use recursion.

If you are walking a DOM tree read from an XML file, on the other hand, you are unlikely to exceed Python's recursion depth (1000 by default). It certainly could, but as a practical matter, it probably won't. When you know what kinds of data you'll be working with ahead of time, you can be confident you won't overflow the stack.

A recursive tree walk is, in my opinion, much more natural to write and read than an iterative one, and the recursion overhead is generally a small part of the running time. If it really matters to you that it takes 16 seconds instead of 14, throwing PyPy at it might be a better use of your time.

Recursion seems a natural fit for the problem you posted and if you think the code is easier to read and maintain that way, and the performance is adequate, then go for it.

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

There are languages that support recursion only limited by memory, and also languages that can optimize tail recursion. Most functional languages do both. (And I only say "most" because I am not 100% sure there aren't any that don't.) — kindall, Nov 25 '10 at 18:45

score 8 · Answer 2 · answered Nov 25 '10 at 15:01

8

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

Most problems occur when new programmers assume recursion is magical and don't realize there is a stack underneath making it possible. New programmers have also been known to allocate memory and never free it, and other mistakes, so recursion is not unique in this danger.

answered Nov 25 '10 at 15:01

President James K. Polk

40,516
21
95
125

1

+1 Always check the requirements of the algorithm, if it blows your stack switch to an iterative solution with your own stack. – Ivo Wetzel Nov 25 '10 at 15:27
Unlikely the "allocate memory and never free it" would occur in Python. ;-) – martineau Nov 25 '10 at 16:29

score 2 · Answer 3 · answered Nov 25 '10 at 18:40

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

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

But both the pure Python function had no chance to be fast, because they do costly operations such as adding lists ala perm[:i] + str[0:1] + perm[i:]

Thanks. I also did the similar test but with s = "012356789" and enabling the gc. In that case the build-in permutations is slower than the recursive one. Do you know why? — Oleg Pavliv, Nov 26 '10 at 17:11

score 0 · Answer 4 · answered Nov 25 '10 at 15:32

I can't reproduce your timing 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

danger of recursive functions

4 Answers4

Linked