Hello, I am an Engineering Manager at Facebook with 13+ years in Ad Technology, Natural Language Processing and Data mining. (Learn More)
by Pravin Paratey

Recursive functions, Stack overflows and Python

Today I was working on a problem that involved a Depth-first search on a graph. The graph had a cycle and I hit the maximum recursion depth for Python (which is 1000).

RuntimeError: maximum recursion depth exceeded

Although I fixed the problem (the graph wasn’t supposed to have cycles), it got me thinking on how Python handles recursion.

Recursion

In short, a recursive function is one which calls itself. A set of functions are recursive if they form a cycle:

Graphical representation of recursion

Head-recursion and Tail-recursion

A recursive function can either be head-recursive or tail-recursive. A function is tail-recursive if the very last thing it does is make a recursive call. Everything else is head-recursive.

A tail-recursive function is of particular interest as it can be transformed by a smart compiler into an iterative loop i.e. a tail-recursive function can be transformed to use constant stack space. This means you don’t have a limit to number of recursive calls you can make.

Unfortunately Python does not automatically optimize tail-recursive calls. Reading what Guido van Rossum had to say on this subject got me thinking even further. Does Python really give me enough power to rewrite recursive functions in a more “Pythonic” way?

Example

Lets look at an example. The following code is a recursive function that prints the factorial of a number:

#!/usr/bin/env python

def factorial(num):
    if num == 0 or num == 1:
        return 1
    else:
        return num * factorial(num - 1)

print factorial(1000)

While factorial(10) prints 3628800, factorial(1000) results in,

  File "factorial.py", line 7, in factorial1
    return num * factorial1(num - 1)
  File "factorial.py", line 7, in factorial1
    return num * factorial1(num - 1)
  File "factorial.py", line 7, in factorial1
    return num * factorial1(num - 1)
  File "factorial.py", line 7, in factorial1
    return num * factorial1(num - 1)
  File "factorial.py", line 7, in factorial1
    return num * factorial1(num - 1)
  File "factorial.py", line 7, in factorial1
    return num * factorial1(num - 1)
  File "factorial.py", line 7, in factorial1
    return num * factorial1(num - 1)
  File "factorial.py", line 7, in factorial1
    return num * factorial1(num - 1)
  File "factorial.py", line 7, in factorial1
    return num * factorial1(num - 1)
  File "factorial.py", line 7, in factorial1
    return num * factorial1(num - 1)
RuntimeError: maximum recursion depth exceeded

factorial() is head-recursive because the result of factorial(num - 1) is multiplied by num before returning. This means that the state of this function has to be saved to the stack before its child is called.

Using decorators

You can use decorators to eliminate tail recursion.

Using reduce

I re-wrote the factorial function using reduce and lambda functions.

#!/usr/bin/env python

def factorial(num):
    return reduce(lambda x, y: x*y, xrange(1,num), 1)

print factorial(1000)

Although not all functions can be re-written this way, Python does have a few tricks up its sleeve. (I know it ends quite abruptly. I kind of lost my train of thought)