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

<?prettify linenums=true?>

``````#!/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.

<?prettify linenums=true?>

``````#!/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)