# Recursion

What is recursion? Typically, this is where we break out the references to Inception.

So let’s go deeper.

## Why Recursion?

What is recursion? Recursion is when a function can call itself. Like this:

``````def donald_trump():
print "Donald Trump!"
print "Who's the most handsome, awesome person in the world?"
print "Hmm, not sure. I know! I'll ask the incredibly knowledgeable"
donald_trump()
``````

Here, the incredibly annoying `donald_trump` function is recrusive because it calls itself.

The opposite of the recursive approach is iteration, whic is what you have been programming in so far. Iteration is doing a series of steps, one at a time, in a linear fashion.

Can every problem that is solved iteratively be solved recursively? Can every problem that is solved recursively be solved iteratively?

Yes! Iterative and recursive approaches to a problem are completely interchangeable. So why bother using recursion?

Recursion is an extremely powerful tool because it allows the programmer to break down problems into smaller instances of itself. So it’s simply a matter of convenience to the programmer. Some problems are much easier to solve recursively, and thinking about it like that allows for easy solutions.

## How to Recurse

Every recursive function needs two critical things:

• A base case
• A way to break up the problem into a smaller problem of the same kind

What’s a base case? Let’s take a look at the `donald_trump` function again. What happens when we call it?

``````>>> donald_trump()
'Donald Trump!'
'Who's the most handsom, awesome person in the world?'
'Hmm, not sure. I know! I'll ask the incredibly knowledgeable'
'Donald Trump!'
'Who's the most handsom, awesome person in the world?'
'Hmm, not sure. I know! I'll ask the incredibly knowledgeable'
'Donald Trump!'
'Who's the most handsom, awesome person in the world?'
'Hmm, not sure. I know! I'll ask the incredibly knowledgeable'
'Donald Trump!'
'Who's the most handsom, awesome person in the world?'
'Hmm, not sure. I know! I'll ask the incredibly knowledgeable'
...
``````

Uh oh… You see the problem. It never stops! This is recursion’s version of the infinite loop: infinite recursion. It never stops recursing! In fact, when you run this, you’ll get a `RuntimeError`.

``````RuntimeError: maximum recursion depth exceeded
``````

What’s a run time error? A runtime error is Python’s way of saying when I looked over your code, I couldn’t find any errors (no type errors, no syntax errors, etc). But when I actually run your code, a mysterious error pops up! This is the standard error Python will give you when you have a case of infinite recursion, so become familiar with it!

A base case is when it finally stops recursing. Let’s put a base in `donald_trump` so he finally stops talking.

``````def donald_trump(num):
if num <= 0:
print "Okay, I'll stop talking now."
return
print "Donald Trump!"
print "Who's the most handsome, awesome person in the world?"
print "Hmm, not sure. I know! I'll ask the incredibly knowledgeable"
donald_trump(num - 1)
``````

Great! Now, eventually, it will stop. In this case, the smaller problem is literally the exact same problem, just with `num` decremented by one.

## Pitfalls

There are usually several common pitfalls when students first start using recursion. Let’s go over them.

1. Infinite recursion

We saw this above with the absurd `donald_trump` example. If you don’t have a base case, you’ll end up in a bad mess.

A problem can have multiple base cases, though. You should carefully examine what the base and recursive cases will be before you start coding to ensure you reach all of them.

1. Return propogation

Often times, our function needs to return something. For some reason, when recursion is introduced, students trip up over the return statement. Let’s go over a basic example.

Imagine that you didn’t have the `len` operator. How could you calculate the length of a list? We could do this recursively!

``````def my_len(some_list, some_number):
if some_list == []:
return some_number
else:
my_len(some_list[1:], some_number + 1)
``````

Will this work? No, it certainly won’t. But why not?

What does the base case do? It checks if the list is empty. If it is, it returns the number that we passed to it. Seems fair enough. Let’s test if the base case works.

``````>>> length = my_len([], 0)
>>> print length
0
>>> length = my_len([], 6)
>>> print length
6
``````

Sure enough, the base case prints whatever the number we passed to it was. Great. What about the recursive case?

``````>>> length = my_len([1], 0)
>>> print length
None
``````

Erm… What? We know from the types lecture that `None` is returned by default if the function does not return anything. That doesn’t make sense though – we are calling another function.

Some of you who are observant will note that calling a function is not the same as returning the value of a called function. And indeed this is the case. We are not returning anything in the recursive case. Having the base case alone return something is not sufficient!

So how do we fix this?

``````def my_len(some_list, some_number):
if some_list == []:
return some_number
else:
return my_len(some_list[1:], some_number + 1)
``````

Sure enough, now that we’re returning the result of the recursive case, this works as expected.

``````>>> print my_len([0, 1, 2, 3, 4, 5, 6], 0)
7
``````

2. Improper subproblem

Sometimes, the second part of recursion where you break up the problem into smaller instances of the same problem can get tricky. Naturally, this depends on the problem at hand. Make sure you’re making the problem smaller (so it actually approaches a base case,) and that it is indeed the same problem.

3. Mutual recursion

Mutual recursion is a special case of recursion when different functions call on each other repetitively, rather than the same function.

``````def even_stuff(number):
if number == 0:
return
print "So much stuff I'm doing! Super important stuff."
odd_stuff(number - 1)

def odd_stuff(number):
print "Secret stuff. Can't know. #PRISM"
even_stuff(number - 1)
``````

Here, we have a pair of functions, `odd_stuff` and `even_stuff`, recursing on each other. Can you guess the output of `odd_stuff(11)`?

Notice that `odd_stuff` doesn’t have a base case here, because it depends on `even_stuff`’s base case. To be really safe, we could write `odd_stuff` in this way instead:

``````def odd_stuff(number):
if odd_stuff < 0:
return
print "Secret stuff. Can't know. #PRISM"
even_stuff(number - 1)
``````

This way we are guaranteed to reach `even_stuff`’s base case on all valid inputs, while ignoring invalid inputs.