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

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