(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:
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?"
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:
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.
You are expected to follow the Stanford Honor Code.
If this is an assignment that allows pairs, the same rules apply to each team. For example, do not look at assignment solutions that do not belong to your team, and do not give your solution to anyone outside of your team.
Remember that we run similarity-detection software over all solutions, including this quarter and past quarters, as well as any solutions we find on the web.
If you need help solving an assignment, we are happy to help you. You can go to the LaIR, or the course message forum, or email your section leader, or visit the instructor / head TA during office hours. You can do it!