Week 11: r e c u r s i o n

Monday

The video from today’s lecture (Monday, April 13, 2020):

And here are the annoucements:

  • Lab 9 is up and due Saturday (Apr 18)

  • Sent out lab 7 grades and midterm grade email

  • Still grading labs 6,8 and quiz 4

Recursion

Any function that sometimes calls itself is known as a recursive function. In most cases, recursion can be considered an alternative to iteration (loops). Instead of defining a loop structure, recursion defines a problem as a smaller problem until it reaches an end point. There are three requirements for a successful recursive function:

  1. Base case: each function must have one or more base cases where the function does not make a recursive call to itself. Instead, the problem has reached its smallest point, and we can begin returning back the small solutions.

  2. Recursive case: the function makes one (or more) calls to itself. The call must use a different argument to the function (or else we keep making the same recursive call over and over again!). Typically, the problem gets 1 smaller.

  3. All possible recursive calls must be guaranteed to hit a base case. If you miss one, your program is susceptible to an infinite recursion bug!

Example: blastoff!

Here is the simple blastoff(n) function, to show a countdown from some number n, using a for loop:

def blastoff(n):
  for i in range(n,0,-1):
    print(i)
  print("blastoff!")

Thinking recursively, you may notice that blastoff(10) is really just this:

print(10)
blastoff(9)

And blastoff(9) is this:

print(9)
blastoff(8)

And so on. The key to writing an algorithm recursively: handle the first item or case, then let recursion handle the rest. For the above, given an integer n, we would:

print(n)           # take care of n
blastoff(n-1)      # let recursion handle the rest

Also note, each subsequent call to blastoff() has a smaller value of n. Eventually we will call blastoff(2), then blastoff(1), and then, finally, blastoff(0). At that point, we want to just print "blastoff" and stop the recursion. This is formally called the base case, and is usually written with an if/else clause.

Here is the full recursive blastoff function:

def recursiveblastoff(n):
   if n <= 0:
      print("blastoff!")
   else:
      print(n)
      recursiveblastoff(n-1)

Notice the base case stops the recursion (does not call another copy). Also notice the non-base case (the else clause) heads toward the base case by calling another copy, but with n-1 as the argument.

Sometimes, to understand recursion, it helps to think about the stack frames. If the above function were called with n=4, how many frames would be put on the stack? Try it in the python tutor! Here is a screenshot of the stack frames, when the recursion has reached the base case:

recursiveblastoff stack frames

Tips for Recursion

For any recursive problem, think of these questions:

  1. What is the base case? In what instances is the problem small enough that we can solve the problem directly? Sometimes you may need more than one base case, but rarely do you need several.

  2. What is the recursive call? Make one or calls in the function to itself. It is very important to use different arguments (usually "smaller") in the recursive call otherwise you obtain infinite recursion.

  3. Do all possible chains of recursion lead to a base case?

  4. If a recursive function is supposed to return a value, make sure all cases return a value and that recursive calls do something with the return value of the smaller problem before returning.

Example: coin flips

Suppose we want to flip n coins and show how many turned up "heads". Here’s the iterative function for that (assuming we have imported the choice(..) function from random:

def flip(n):
    """flip n coins, return number of heads"""
    count = 0
    for i in range(n):
        flip = choice(["heads","tails"])
        if flip == "heads":
            count = count + 1
    return count

For the recursive version, how can we just flip 1 coin, and then let the recursive function handle the other n-1 flips? The key is trusting that recursiveflip(n-1) will give back the correct answer!

So recursiveflip(5) is the same as flipping 1 coin and then adding how many "heads" we get from recursiveflip(4).

And what’s the base case? If each recursive call has one less flip to do, eventually we will get to recursiveflip(0), and that should return 0 (the number of "heads" resulting from flipping 0 coins).

def recursiveflip(n):
    """flip n coins using recursion, return number of heads flipped"""
    if n <= 0:
        return 0
    else:
        flip = choice(["heads","tails"])
        if flip == "heads":
            count = 1
        else:
            count = 0
        return count + recursiveflip(n-1)

Example: in list

How about inlist(x,L), which returns True if x is found in the list L, and False if not?

Slicing reminder

Before we write inlist(x,L), let’s review slicing in python. Slicing lets you easily look at subsets of strings or lists. The general syntax is S[i:j]. This gives the substring of S starting at index i and running up to but not including index j.

$ python3
>>> hw = "hello world"
>>> hw[1]
'e'
>>> hw[7:10]
'orl'
>>> hw[0:5]
'hello'
>>> hw[6:]
'world'
>>> hw[:5]
'hello'

You can also omit i or j. S[i:] gives you the substring starting at index i and running to the end of that string. S[:j] gives you the substring up to but not including the j-th character.

Note: slicing can also be used with lists e.g. if L = [1,2,3,4,5], then L[2:4] is [3,4].

Now back to the inlist(x,L) example:

x = 5
L = [1,6,5,9,7]

How can we handle just one part of looking for x in L? Let’s just examine the L[0] item, then let the recursion look for x in L[1:] (the rest of the list).

And what’s the base case? If each time we recur with a smaller and smaller list, eventually we will have and empty list ([]).

def inlist(x,L):
    """return True if x in L, False if not"""
    if len(L) == 0:
        return False   # base case, nothing left in list, so x not found
    else:
        if x == L[0]:
            return True     # found x, no need to recur
        else:
            result = inlist(x,L[1:])   # keep looking
            return result              # return whatever we find

Wednesday

The video from today’s lecture (Wed, April 15, 2020):

Lots of small practice problems today!

Here’s what we worked on in the breakout rooms:

  • recursive sum of a list

  • recursive count how many of x are in list L

  • recursive reverse a string

sum a list

For this one, how can we do just one small part of the summation? If we have a function (nevermind that we are currently writing it!) called rsum(L) that returns the sum of a list, then recursively, the sum of L can be written as L[0] + rsum(L[1:]) (first item plus sum of the rest of the items).

This means we will be recurring on smaller and smaller lists, which leads us to the base case: what should this function return when the list is empty? What it the sum of an empty list?

Here’s one way to write rsum(L):

def rsum(L):
    """use recursion to sum a list"""
    if len(L) == 0:
        return 0
    else:
        return L[0] + rsum(L[1:])

Many students see that and ask, isn’t the final return 0 being sent back to main? Here’s the stack diagram for the recursive sum function:

recursive sum stack frames

The base case stack frame returns 0 to the previous call of rsum, which returns it’s L[0] plus the base case’s 0 to the rsum call before that, which returns it’s L[0] and so on…​

count x in L

We’re looking to count how many of x are in L. Again, how can we do just the first part (i.e., count the first item), then let recursion handle the rest?

If we were doing an accumulator, we would do something like this:

count = 0
if x == L[0]:
    count = count + 1

Letting recursion count the rest means again sending the rest of the list (L[1:]) to another copy of the function. Since the list is getting smaller and smaller with each recursive call, the base case is "how many of x are in an empty list?".

def rcount(x,L):
    """use recursion to count how many of x are in L"""
    if len(L) == 0:
        return 0
    else:
        count = 0
        if x == L[0]:
            count = count + 1
        return count + rcount(x,L[1:])

Friday

The video from today’s lecture (Friday, April 17, 2020):

And here are the annoucements:

  • Finished grading quiz 4, quiz 5 will be next week

  • Quiz 5 is on files, searching, and sorting

  • Ninja session tonight, office hours today

  • Still grading lab 8

go over quiz 4 files

Ask me if you still don’t understand any of the questions from Quiz 4!

recursive stack example

See stackexample.py…​.draw stack for rsum(L) function.

stack example

merge sort

Edit sorts.py, add mergeSort(L) function.

def mergeSort(L):
    """sort list using merge sort"""
    if len(L) > 1:
        # split into two lists
        half = len(L)//2
        L1 = L[:half]
        L2 = L[half:]
        # sort each list
        mergeSort(L1)
        mergeSort(L2)
        # merge them back together
        merge(L1,L2,L)

Run timing.py to compare merge vs selection sort.

Merge sort is an O(NlogN) sort!

merge sort in NlogN