Week 11: Recursion
Lab 9 is available now.
Week 11 Topics
Iteration vs recursion
Recursion on lists and strings
(time permitting) Recursion using Graphics
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:
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.
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.
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: Print a Message
printmessage.py program prints a given message
n times. We’ve already
seen how to solve this problem with a loop, but let’s explore how we can solve
it without a loop using recursion. To understand what’s happening with
recursion, it’s often helpful to draw a stack diagram. The key concept is that
Python treats the recursive function call the same as any other function
call — it places a new stack frame on top and begins executing the new function.
The only difference is the function in this case has the same name.
Example: Summing Integers
We are going to write some iterative and recursive versions of the same
function. Iterative versions use loops, recursive versions do not use loops,
and instead contain calls to themselves but on a smaller problem. I’ve given
you the code for an algorithm we have seen before — a
for loop that sums all
def iterativeSum(n): total = 0 for i in range(n): total = total + (i+1) return total
Together, we’ll write a recursive function that accomplishes the same task.
Tips for Recursion
For any recursive problem, think of these questions:
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.
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.
Do all possible chains of recursion lead to a base case?
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.
Recall the iterative version (using a loop) of factorial that takes a positive
n, and returns the product of the first n integers. Try writing a
recursive version of the factorial function in
Exercise: Interpret a Recursive Function
countdown.py, and working with a neighbor, do the following:
Explain the program to your neighbor.
What is the recursive function doing?
Identify the base vs recursive case?
Are you sure that all recursive calls eventually hit the base case?
Assuming the user inputs
4, draw a stack diagram at the time the program prints "blastoff".
Before moving on to more recursion examples, we’ll briefly remind you about a
Python operator called slicing that can be particularly useful when working
with recursion. Slicing lets you easily look at subsets of strings or lists.
The general syntax is
mystr[i:j]. This gives the substring of
starting at index
i and running up to but not including index
$ python3 >>> hw = "hello world" >>> hw 'e' >>> hw[7:10] 'orl' >>> hw[0:5] 'hello' >>> hw[6:] 'world' >>> hw[:5] 'hello'
You can also omit
mystr[i:] gives you the substring starting at
i and running to the end of that string.
mystr[:j] gives you the
substring up to but not including the
Note: slicing can also be used with lists e.g. if
lst = [1,2,3,4,5], then
Exercise: Reversing a List
Next, we’ll use recursion to work with lists. In
listReverse.py, write a
function that takes in a list and returns a new list that contains the input
list’s items in reverse order.
So far, most of the recursion problems we’ve seen could have been solved just as easily (or even more easily) with iteration. Next, we’ll consider a famous sorting algorithm, merge sort, that naturally uses recursion.
Finally, let’s look at a (yet another) attempt to draw trees using the graphics library. This time, we’ll draw the branches of a tree recursively!