Due Tuesday, July 19 at 11:59 pm Pacific
- Submissions received by due date receive a small on-time bonus.
- All students are granted a pre-approved extension or "grace period" of 24 hours after the due date. Late submissions are accepted during the grace period with no penalty.
- The grace period expires Wed, Jul 20 at 11:59 pm Pacific, after which we cannot accept further late submissions.
- In this course, we express all date/times in Pacific time GMT -7. Our Paperless submission system also displays/records due dates and submission times in Pacific time.
Attribution: This assignment was designed by Julie Zelenski
Recursion is a powerful problem-solving tool with tons of practical applications. This assignment consists of a "sampler" of different recursion problems each of which is interesting in their own way. Learning to solve problems recursively can be challenging, especially at first. We think it's best to practice in isolation before adding the complexity of integrating recursion into a larger program ā we'll get to incorporating recursion into a large program at the end of the quarter! By the time youāre done with this assignment, we think youāll have a much deeper appreciation both for the art of recursive problem-solving and the types of probelms that you can solve with your newfound skills.
Most students find that it takes some time to get comfortable thinking recursively. We recommend that you start the assignment early. Read over the problem statements today and get your brain starting to mull it over. There is not a large amount of code for you to write, but you want to give yourself plenty of time to wrap your head around this new way of solving problems. And while that beautiful recursive solution may be only a few elegant lines, you'll work hard on each line. Recursive code can be dense and complex and requires your full attention to get the details just right.
Dedicate yourself to deeply assimilating the foundation concepts within the context of these small, targeted problems. Lecture will continue on to explore more advanced applications of recursion. By the end of this week, you'll be in prime shape to tackle recursive solutions for even more impressive problems.
All assignments in CS106B must be completed individually. Working in pairs/groups is not permitted.
Learning goals
After completing this assignment, you will be able toā¦
- Appreciate the elegance and power of recursive problem-solving and identify problems that are well-suited to be solved recursively.
- Understand and trace how data is stored and altered across multiple recursive function calls.
- Identify and carry out techniques for testing and debugging recursive functions.
- Break down a problem into a collection of smaller, self-similar tasks.
- Develop a recursive algorithm by dividing a problem into one or more base cases and one or more recursive cases.
- Apply the general frameworks of recursive backtracking to solve problems that cannot easily be solved using an iterative approach.
- Implement more advanced recursive algorithms to solve problems that cannot be easily solved using an iterative approach
Assignment parts
This assignment consists of a collection of multiple different recursive exercises, grouped into two parts.
Part 1: Fundamental Recursion
The first collection of recursive problems walks you through some fundamental recursion problems that increase in difficulty and complexity over time. These problems will serve as the foundational practice for you to begin to grapple with the core tenets of recursive problem-solving. The material needed to solve these problems was covered in lecture on Tuesday and Wednesday (7/5 and 7/6).
-
Fundamental Recursion Warmup
Practice with unit tests and debugging on recursive functions.
-
Balanced Operators
Determine whether an expression has properly matched pairs of bracketing characters.
-
Sierpinski Fractal
Draw a beautiful self-similar fractal triangle.
-
Merging Sorted Sequences
Implement an efficient divide-and-conquer algorithm for merging a collection of sorted sequences.
Part 2: Recursive Backtracking
The second collection of recursive problems pivots towards applying the powerful nature of recursive backtracking to solve some real-world problems. After you've built your solid base of recursive fundamentals in Part 1, you will be well set to apply your newfound skills to solve some practical real-world problems. The material needed to work through the debugging warmup for this part will be covered on Tuesday (7/12). By Wednesday (7/13), you should be equipped to solve all problems in this part of the assignment.
-
Recursive Backtracking Warmup
Practice with unit tests and debugging on core recursive functions.
-
Scoring Boggle
Find all words on a given Boggle board and tally the maximum possible score.
-
Optional Extra Credit Problem - Examining Voting Systems
Put the finishing touch on your journey to being a recursive problem-solving master by completing this optional challenge problem, which involves investigating block voting systems (like the U.S. Electoral College).
Getting started
We provide a ZIP of the starter project. Download the zip, extract the files, and open the .pro file in Qt Creator.
š¦ Starter code
The source files you will edit are fundamentalwarmup.cpp
(accidentally named findamentalwarmup.cpp
), balanced.cpp
, sierpinksi.cpp
, merge.cpp
, backtrackingwarmup.cpp
, and boggle.cpp
.
Additionally, you will answer questions in short_answer.txt
.
Resources
Here are some resources that you might find helpful for this assignment:
- The CS106B Guide to Testing
- The CS106B Style Guide
- Resolving Common Build/Run Errors, compiled by section leader Jillian Tang.
- Lectures: Big O, Intro. to Recursion, Fractals
- Section: Week 3 section on recursion, week 4 Section on recursive backtracking
- Textbook Chapters 7, 8, and 9. These chapters are a great resource āthe explanations and examples for recursion are Eric Roberts at his very best. Eric is our long-time Stanford colleague and a gifted educator.
- Stanford Professor, emeritus Eric Robert's Thinking Recursively
Getting help
Recursion can take some time to get used to, so donāt be dismayed if you canāt immediately sit down and solve these problems. Ask for advice and guidance if you need it. Once everything clicks, youāll have a much deeper understanding of just how cool a technique this is.
Look for an announcement on the Ed forum for the YEAH session for this assignment. If you have questions for us, the Ed forum is open 24/7 for general discussion. Always start by searching first to see if your question has already been asked and answered before making a new post. To troubleshoot a problem with your specific code, your best bet is to bring it to the LaIR helper hours or office hours.
Submit
Before you call it done, run through our submit checklist to be sure all your t
s are crossed and i
s dotted. Then upload your completed files to Paperless for grading.
Please submit only the files you edited; for this assignment, these files will be:
fundamentalwarmup.cpp
(accidentally namedfindamentalwarmup.cpp
- please leave the name as that!)balanced.cpp
sierpinksi.cpp
merge.cpp
backtrackingwarmup.cpp
boggle.cpp
short_answer.txt
voting.cpp
(optional)
š Submit to Paperless
Note: On Paperless, all due dates and submission times are expressed in Pacific time.