What is recursion? Typically, this is where we break out the references to Inception.
So let’s go deeper.
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.
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: 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.
There are usually several common pitfalls when students first start using recursion. Let’s go over them.
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(, 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,
even_stuff, recursing on each other. Can you guess the output of
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.