Algorithm-Preparation: Recursion

Suppose you're digging through your grandma's attic and come across a mysterious locked suitcase. Grandma tells you that the key for the suitcase is probably in this other box. This box contains more boxes, with more boxes inside those boxes. The is in a box somewhere. What's your algorithm to search for the key? Think of an algorithm before you read on.

Here's one approach:

1. Make a pile of boxes to look through.
2. Grab a box, and look through it.
3. If you find a box, add it to the pile to look through later.
4. If you find a key, you're done!
5. Repeat.

Here's an alternate approach:

1. Look through the box.
2. If you find a box, go to step 1.
3. If you find a key, you're done!

Which approach seems easier to you?

The first approach uses a while loop. While the pile isn't empty, grab a box and look through it:

def look_for_key(main_box):
    pile = main_box.make_a_pile_to_look_through()
    while pile is not empty:
        box = pile.grab_a_box()
        for item in box:
            if item.is_a_box():
                pile.append(item)
            elif item.is_a_key():
                return "found the key!"

The second way uses recursion. Recursion is where a function calls itself. Here's the second way in pseudo-code:

def look_for_key(box):
    for item in box:
        if item.is_a_box():
            look_for_key(item)
        elif item.is_a_key():
            return "found the key!"

Both approach accomplish the same thing, but the second approach is clearer to me. Recursion is used when it makes the solution clearer. There's no performance benefit to using recursion; in fact, loops are sometimes better for performance.

Many important algorithms use recursion, so it's important to understand the concept.