Due Friday, October 15 at 11:59 pm
- Submissions received by the due date receive a small on-time bonus.
- All students are granted a pre-approved extension or "grace period" of 48 hours after the due date. Late submissions are accepted during the grace period with no penalty.
- The grace period expires Sun, Oct 17 at 11:59 pm, after which we cannot accept further late submissions.
- All due dates and submission times are expressed in Pacific time.
Recursion is a powerful problem-solving tool with many practical applications. This week's assignment is a recursion "sampler" that introduces recursive problem-solving through several small, independent tasks. 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 that in future assignments!
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 next week, you'll be in prime shape to tackle recursive solutions for even more impressive problems.
This assignment is to be completed individually. Working in pairs/groups is not permitted.
After completing this assignment, you will be able to…
- 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.
- Understand and trace execution through recursive function calls.
- Apply techniques for testing and debugging recursive functions.
This assignment consists of a short warmup exercise and four recursive functions.
Practice with unit tests and debugging on recursive functions.
Determine whether an expression has properly matched pairs of bracketing characters.
Help Karel find the way home by counting possible routes to the origin.
Draw a beautiful self-similar fractal triangle.
Implement an efficient divide-and-conquer algorithm for merging a collection of sorted sequences.
We provide a ZIP of the starter project. Download the zip, extract the files, and open the .pro file in Qt Creator.
The source files you will edit are
Additionally, you will answer questions in
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: Monday Intro to Recursion, Wednesday Big O, Wednesday Recursive Fractals
- Section: Next week's section on recursion
- 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
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.
Before you call it done, run through our submit checklist to be sure all your
ts are crossed and
is dotted. Then upload your completed files to Paperless for grading.
Please submit only the files you edited; for this assignment, these files will be:
Note: On Paperless, all due dates and submission times are expressed in Pacific time.