recursive function: use a global or pass a parameter?

Gregory Ewing greg.ewing at canterbury.ac.nz
Sat Jan 17 22:25:42 CET 2015


Yawar Amin wrote:

> Cool ... but it looks like this can still potentially hit the max
> recursion limit?

It depends on the nature of your data. If the data is
a tree, it's very unlikely you'll reach the recursion
limit unless the tree is massively unbalanced.

If there's a chance of that, or if the data structure
is really a graph that could contain long linear
chains, then a non-recursive solution is safer.

Incidentally, Python's pickle suffers from this
problem -- it's possible to create a structure that
can't be pickled due to excessive recursion depth:

 >>> x = []
 >>> for i in range(5000):
...  x = [x]
...
 >>> import pickle
 >>> s = pickle.dumps(x)
Traceback (most recent call last):
   File "<stdin>", line 1, in <module>
RuntimeError: maximum recursion depth exceeded while pickling an object

Fortunately, the kinds of structures that cause this
tend not to be used in Python, e.g. we normally use
Python list objects instead of linked lists. So most
of the time, pickle gets away with using recursion.

-- 
Greg



More information about the Python-list mailing list