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:

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.