Week 11: Recursion

Lectures:

You must be logged on to your swarthmore.edu account for the youtube lecture videos to be viewable

Introduction

The key idea of recursion is to solve a problem by breaking it down into a smaller version of the same problem.

In other words, we can define a function in terms of itself.

A function which calls itself is known as a recursive function.

Can you really define something in terms of itself? Isn’t this a circular definition?

Recursion on numbers

In mathematics, recursive definitions are common. For example, consider factorial.

               | if n is 0     1
factorial(n) = |
               | otherwise     n * factorial(n-1)

You can see that the recursive definition is not circular because each application causes you to request the factorial of a smaller number. Eventually you will get down to 0, and the recursion will end.

factorial(4) = 4 *   factorial(3)
             = 4 *   3 *    factorial(2)
             = 4 *   3 *    2 *       factorial(1)
             = 4 *   3 *    2 *       1 *      factorial(0)
             = 4 *   3 *    2 *       1 *      1
             = 24

All good recursive definitions have these two key characteristics:

  1. There are one or more base cases for which no recursion is required.

  2. All recursive calls eventually end up at one of the base cases.

The simplest way to guarantee that these two conditions are met is to make sure that each recursion always occurs on a smaller version of the problem.

Here’s how we would write factorial as a recursive python function:

def factorial(n):
   if n == 0:   # base case
      return 1
   else:        # recursive case
      return n * factorial(n-1)

And here’s how we could test it (we would expect the answer to be 6):

result = factorial(3)
print("factorial of 3 is", result)

Implement this function with the test code in the python tutor. Remember that in the python-tutor the stack grows downward, whereas in class we draw the stack as growing upward.

Recall that when we do a stack diagram, every function call adds a new frame onto the stack. So how many stack frames should we expect to appear when we call factorial(3)? Think about your answer and then trace through the execution line by line.

Let’s write another recursive function on numbers. We want to compute the summation of numbers starting at 0 and going up to and including n. This looks very similar to the factorial function.

def summation(n):
   if n == 0:
      return 0
   else:
      return n + summation(n-1)

We could easily have written both of these functions with a loop rather than with recursion. For example, here are the loop versions of both factorial and summation.

def factLoop(n):
   result = 1
   for i in range(1,n+1):
      result = result * i
   return result

def sumLoop(n):
   result = 0
   for i in range(n+1):
      result = result + i
   return result

So why do we need recursion? Actually it isn’t necessary, however, in some cases a recursive solution will be much clearer to understand and easier to implement than iterative versions that use loops.

Try implementing and tracing through one of these iterative versions in the python tutor. You’ll see that when executing an iterative solution, only one copy of the function will appear on the call stack. Therefore recursive solutions have some cost associated with them, so we don’t want to start using them to solve every problem. You’ll still want to typically use for and while loops, but there will be occasions where recursion is your best option.

Slicing

First, we need to learn about slicing lists, which will allow us to do recursion on smaller and smaller versions of a given list.

When you slice a list it allows you to grab out a subset of the list into a new list.

Syntax:

<list_name>[<start_index>:<end_index>]

Semantics:

  • Grab the subset of the list from the <start_index> up to, but not including the <end_index>

  • If the <end_index> is omitted, continue all the way to the end of the list

  • If the <start_index> is omitted, begin at the first item in the list

  • If both the <start_index> and the <end_index> are omitted, grabs the entire list effectively making a copy of it

Here are some examples:

ls = [5, 10, 15, 20, 25, 30]
      0  1   2   3   4   5

ls[1:3] => [10, 15]
ls[2:] => [15, 20, 25, 30]
ls[:3] => [5, 10, 15]
ls[:] => [5, 10, 15, 20, 25, 30]

Recursion on lists

Now that we know how to use slicing, let’s try to write a recursive function that will sum up the numbers in a list.

When creating the base case, think about the easiest version of the problem someone could give you such that you could immediately know the answer, without doing any work.

Often when doing recursion on lists, the easiest problem is the empty list. What is the sum of an empty list? Answer: 0.

When creating the recursive case, think about how you could do just a little bit of the work, and make the problem smaller so that you will eventually reach the base case.

When summing up a list, we can take off the first element and add that on to the result of summing up the rest of the list.

def sumList(ls):
   if len(ls) == 0:
      return 0
   else:
      return ls[0] + sumList(ls[1:])

Recursion on strings

In python, you can slice strings in the same way that you do lists.

Suppose we wanted to write a function called replace(string, old_chr, new_chr) that would take a string and would create a new string where each instance of the old_chr was replaced with new_chr.

For example, replace("banana", "a", "i") would return "binini" and replace("hello", "l", "y") would return "heyyo".

Let’s write a recursive solution to this problem.

You should always begin by thinking about the base case.

Question: What is the easiest string someone could give this function, where you could immediately give them the final result?

Answer: The empty string! There’s nothing to replace in it.

Next you should think about the recursive cases.

Question: How could we make a little bit of progress on solving this problem and then use recursion to complete the rest of the work?

Answer: Let’s check the first character in the string.

If it equals the old_chr then concatenate the new_chr on to recursively replacing throughout the rest of the string.

If it does not equal the old_chr then concatenate the current first charachter on to recursively replacing throughout the rest of the string.

def replace(string, old_chr, new_chr):
   """
   Inputs: A string and two characters
   Returns: A new string where every instance of the old_chr is replaced
            by the new_chr
   """
   if len(string) == 0:
      return ""
   elif string[0] == old_chr:
      return new_chr + replace(string[1:], old_chr, new_chr)
   else:
      return string[0] + replace(string[1:], old_chr, new_chr)