CSci 150: Foundations of computer science
Home Syllabus Readings Projects Tests

Recursion on sequences

A first example

Suppose we want a function that take a parameter string containing digits and should return the sum of all those digits. For instance, “add_digits('31415')” should compute and return 14, from 3 + 1 + 4 + 1 + 5.

You might easily imagine doing this using a for loop to iterate through each character in the string. But right now I want to reflect on the alternative technique implemented in the following definition.

def add_digits(numstr):
    if len(numstr) == 1:
        return int(numstr)
    else:
        sum_rest = add_digits(numstr[1:])
        return int(numstr[0]) + sum_rest

This implementation is a departure from what we've seen before because here we have a function — named add_digits — that ends up calling itself. A function calling itself, such as this one, is called a recursive function.

To see how this works, let's consider what happens when somebody calls “add_digits('314')”.

  1. We enter add_digits with the parameter numstr being “314”. Since this string's length is more than one, we enter the else clause.

  2. Inside the else, we first compute numstr[1:], which is the string “14”. Then we pass this string as a parameter to add_digits.

    1. Now we enter add_digits with the parameter numstr being “14”. Since this string's length is more than one, we enter the else clause.

    2. Inside the else, we first compute numstr[1:], which is the string “4”. Then we pass this string as a parameter to add_digits.

      1. Now we enter add_digits with the parameter numstr being “4”. Since this string's length is one, the if clause.

      2. Inside the if, we compute the integer to which the string corresponds, yielding the integer 4, which we return.

    3. Having received 4 from the recursive call, we store that in the sum_rest variable. The next line finds what integer the first digit in numstr corresponds to — and at this level, numstr is “14”, so the first digit is the integer 1 — and adds to that the value in sum_rest, which is 4. The function returns this sum, 5.

  3. Having received 5 from the recursive call, we store that in the sum_rest variable. The next line finds what integer the first digit in numstr corresponds to — and at this level, numstr is “314”, so the first digit is the integer 3 — and adds to that the value in sum_rest, which is 5. The function returns this sum, 8.

Rules of recursion

Here are three things to keep in mind as you write recursive functions yourself.

  1. Each recursive function must have a base case — some situation where the function is not recursive. After all, if there is no function, the function will always call itself, and it will never get around to returning. (In fact, since each recursive call takes up a bit of memory, eventually the program will exhaust the memory available to it, and the computer will crash it.)

    In the case of add_digits, the base case is when the parameter string is just one character long.

  2. Whenever there is recursion, the argument passed will be “smaller” than it was originally — that is, it will be closer to a base case. For example, the add_digits function calls itself with a string that is one digit shorter than the string it was given, so the lower-level call works with something that is closer to the base case of a one-character string.

  3. In handling the recursive case of a recursive function, it's helpful to think in terms of the magical assumption: Assume your function somehow magically works correctly for any argument smaller than the argument you're interested in. How can you use that to solve the problem for your parameter?

    (By the way, the term “magical assumption” is just a phrase that I made up. And of course, there's nothing that's actually magical about recursion.)

Another example: Reversing

Now let's consider how you can build your own recursive function. Let's build a recursive function that, given a string, returns a string with the letters reversed. For example, reverse('straw') should return the string 'warts'.

We start by reminding ourselves of the magical assumption: If we have a n-character string to reverse, how can the magical ability to reverse anything shorter than that help us to reverse an n-character string?

Here's an idea: Let's suppose we take everything but the first letter — traw — and reverse that to get wart. Then we just have to add the first letter after it. We implement this idea as follows.

def reverse(word):          # We're not done yet!
    first = word[0]
    rest = word[1:]
    rest_reversed = reverse(rest)
    return rest_reversed + first

Of course, you have to wonder: How is it going to work on traw? Well, it'll go through the same procedure: Reverse raw to arrive at war and add a t on that to get wart.

But how does it reverse raw? It reverses aw to arrive at wa and adds an r to get war. And how does it reverse aw? It reverses w to arrive at w and adds a a to get wa.

But now things get a bit sticky. In reversing w, our program will let rest be the empty string, and it will reverse the empty string. But in reversing the empty string, the program will attempt to assign first to be the first letter, and at that point the program will crash.

What we need is a base case: some situation where no recursive calls are made. Every recursive function needs a base case so that it eventually terminates. In this case, our base case will be when we're asked to reverse a one-letter word: In that case, the word is the reverse of itself, so we can simply return that without any further processing. Adding that case gives us a complete, working function.

def reverse(word):
    if len(word) <= 1:
        return word
    else:
        first = word[0]
        rest = word[1:]
        rest_reversed = reverse(rest)
        return rest_reversed + first

(By the way, this isn't the only possible answer. A very different approach would be to observe that we can reverse straw by dividing the string down the middle into two halves,st and raw, reversing each of those using the magical assumption, and then appending war and ts.)

For now, we're focusing on recursive functions that work in a particular way: We are dealing with a sequence such as a list or string as a parameter, and we are working recursively toward a base-case of a one-element sequence. The examples you get this way aren't particularly compelling, since you can easily imagine doing them with for or while loops, but it's the simplest place to start. We'll see later some more complex applications of recursion.