Lecture Preview: Recursion

(Suggested book reading: Programming Abstractions in C++, 7.1-7.2, 7.5-7.7)

Today we will introduce recursion. This is one of my favorite topics in the course! Recursion is a way of taking a big problem and repeatedly breaking it into smaller and smaller pieces until it is so small that it can be so easily solved that it almost doesn't even need solving.

There are two parts of a recursive algorithm:

  • base case: where we identify that the problem is so small that we trivially solve it and return that result.
  • recursive case: where we see that the problem is still a bit too big for our taste, so we chop it into smaller bits and call ourself (the function we are in now) on the smaller bits to find out the answer to the problem we face.
Think of recursion as moving a mountain one pebble at a time by repeatedly breaking it in half until each piece is the size of a pebble, and then moving the pebbles. It's very Zen.

Here is an example very applicable to large classes. Lets say we want to count how many people are in one "column" of seats in the class. I ask the person in the front row, "How many people are in your column?"

class count

How can we solve this recursively? We need a base case and a recursive case. The recursive case is to delegate the problem (in slightly smaller form) to the person behind you. You can take their answer and add one, that's pretty easy! The base case is the person in the very back. They can just say "zero", that's pretty easy! So we took a problem that was potentially a lot of work and made it into one of two cases, each of which is pretty easy. You might be wondering, how do we get from the person in the front row to the person in the back row, what happens in the middle? Well, the people in the middle are facing really the same situation as the person in the front, so they also follow the recursive case (in a sense they "don't know" they're in the middle). Here's a picture:

class count pt.2

Once you get the hang of recursion, you'll find it a powerful and elegant tool. If, at first, it makes your brain feel like it is being twisted into a pretzel, please know that you are not alone! We'll work through many different examples, and poke and dissect the inner workings of recursion. You'll take different lessons from each example, and over time it will start to feel more natural for you.

This document and its content are copyright © Marty Stepp, 2015. All rights reserved. Any redistribution, reproduction, transmission, or storage of part or all of the contents in any form is prohibited without the authors' expressed written permission.