How to Use Recursion in Python

Now that we know recursion is characterized by the use of a function that calls itself, let's have a look using the textbook example of the fibonacci sequence.

For the uninitiated, the fibonacci sequence goes something like this: 1, 1, 2, 3, 5, 8, 13, 21, 34. Each subsequent number is obtained by summing the previous two numbers.

A recursive algorithm to generate the nth number in the sequence would look something like this:

def fibonacci(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

To wrap your head around this, let's use the call of fibonacci(4) as an example.

When you call the above function with a value of 4, the function will hit:

return fibonacci(3) + fibonacci(2)

We don't know the solution to either of these, so we call fibonacci(3) first:

return fibonacci(2) + fibonacci(1)

Again, we don't know the solution to fibonacci(2), so we call that which hits:

return fibonacci(1) + fibonacci(0)

Great! This is a problem small enough for us to solve so both of those calls to our function return 1. Then, we end up back at:

return fibonacci(2) + fibonacci(1)

Except this time, fibonacci(2) has a value of 2 so then fibonacci(1) is called. This quickly returns 1 so now we have completely resolved fibonacci(3) from the first iteration. It evaluates to 3!

Now we just have to deal with fibonacci(2). This hits:

return fibonacci(1) + fibonacci(0)

Which returns a value of 2. Our function terminates with a final evaluation of 2 + 3. We return the value 5.

Now wasn't that easy? No? That's fine, it still melts my brain.

Here's a summary of the functions indented by what level the calls actually occur:

fibonacci(4)
    fibonacci(3)
        fibonacci(2)
            fibonacci(1)
                = 1
            fibonacci(0)
                = 1
        fibonacci(1)
            = 1
    fibonacci(2)
        fibonacci(1)
           = 1
        fibonacci(0)
            = 1

Fibonacci is a decent way to demonstrate recursion unfortunately, it is purely academic. It has no real world value since an iterative algorithm is much easier to read and works faster. Let's move on to some more practical examples.

A palindrome is a phrase that is the same written forward and backwards. "Madam, I'm Adam" and "rotator" are both palindromes. Now how would you write an algorithm to test for palindromes using a for or while loop? It's doable, but not so simple. It turns out, this is a perfect application for breaking the problem into smaller problems we can solve easily and using, you guessed it, recursion!

# assume we have made sure w is a lowercased phrase stripped of spaces and punctuation
def isPalindrome(w):
    if len(w) == 1:
        return True
    elif len(w) == 2:
        if w[0] == w[1]:
            return True
        else:
            return False
    else:
        if w[0] == w[-1]:
            return isPalindrome(w[1:-1])
        else:
            return False

I'll spare you the stack trace. You'll see our two small problems we know how to solve (our base cases).

If a word is 1 character, it is necessarily a palindrome. If it is 2 of the same characters, it is a palindrome as well.

If it is longer than that, we don't know. We check the first and last letters to make sure they're the same then recursively call our function with w[1:-1] which is the same phrase without the outer two letters.

Here's an output of log statements from calling "isPalindrome('madamimadam')":

calling isPalindrome on madamimadam
comparing m to m
calling isPalindrome on adamimada
comparing a to a
calling isPalindrome on damimad
comparing d to d
calling isPalindrome on amima
comparing a to a
calling isPalindrome on mim
comparing m to m
calling isPalindrome on i
It is a palindrome!

See how recursion allows us to solve the smallest case of a problem, then apply it on a much wider scale by breaking our large problem into smaller pieces?

Is the palindrome example still too contrived for you? Well how about this one?

Let's say you are writing a python script to find all of the image files in a given directory and its subdirectories and do something with them, say append something to their name. If you did not do this recursively, you're looking at a huge headache. Who knows how deep the directory structure goes? Yes, Python has a built in method "os.walk" that does this for you, but it's possible you'll need to be more flexible and need to implement this yourself. Here goes!

def appendToImages(dir, image_file_extensions=['jpg', 'jpeg', 'gif', 'png']):
    filenames = os.listdir(dir)

    for filename in filenames:
        filepath = os.path.join(dir, filename)

        if os.path.isfile(filepath):
            # ignore non image files
            filename, file_extension = os.path.splitext(filepath)
            if not file_extension[1:] in image_file_extensions:
                continue

            os.rename(filename + file_extension, "{0}-IMAGE{1}".format(filename, file_extension))
            print("renamed {0}{1} to {0}-IMAGE{1}".format(filename, file_extension))
        elif os.path.isdir(filepath):
            appendToImages(filepath)

To quickly summarize, we take a directory, list its files, then iterate over those files. If it is in fact a file, we decide if it is an image and work on it. If it is a directory, we call "appendToImages" on that directory.

The first thing about recursion that trips up new programmers is termination. Your function must have a termination condition that is reached 100% of the times it is called. If not, you will have an infinite loop that sucks up memory until it stack overflows or crashes. In the above scripts, we either act upon a number that decreases each time the function is called or we can assume the list of files is finite.

When should you use recursion?

This is a tough answer, since any recursive algorithm could be written iteratively. My recommendation is to become comfortable with recursion, learn about recursive sorting and searching algorithms, then use it when it feels like you are solving the same problem over and over with a smaller set of data each time. There are performance concerns as well. Many recursive algorithms are slower than their iterative counterparts, but that is a guide for another day.