Assign3: Recursive Problem Solving
Due Thursday, July 16 at 11:59 pm
- The assignment deadline is by the end of the day in Pacific Daylight Time. This means that you have until 11:59pm PDT on the day of the assignment deadline to submit the assignment.
- Submit by the end of the day Thursday deadline for a small, “early-bird” bonus.
- All students have a pre-approved extension or "grace period" that extends until Friday end of the day PDT, with no penalty.
- The grace period expires at the end of the day Friday, after which we cannot accept further late submissions.
- Note that our Paperless submission system displays due dates and submission times in the PDT frame of reference.
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.
For almost all students, recursive problem-solving can take a non-trivial amount of time to get used to. We recommend that you start on this assignment as early as possible, so as to allow yourself enough time to wrap your head around this new way of solving problems. In particular, we strongly recommend revisiting the lecture slides and examples, working through the Week 3 section probelms, and joining the discussion on Ed as you come across challenging questions. The recursive solutions you need to write to solve this collection of problems may be not require many raw lines of code, but this doesn't mean that you should put the assignment off until the last minute. While you may not have to write many lines of code, most of your time should be spent thinking through the recursive structure of the problem and really nailing down a detailed problem-solving approach in pseudocode before trying to code up the solution. By putting in the time to nail down the recursive fundamentals now, you'll be in prime shape to tackle recursive solutions for even more impressive problems later on in the course!
This assignment is to be completed individually. Working in pairs/groups is not permitted.
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
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 tenants of recursive problem-solving. The material needed to solve these problems was covered in lecture on Monday-Wednesday (7/6-7/8).
Practice with unit tests and debugging on core recursive functions.
Determine whether a snippet of code has properly matched pairs of bracketing characters.
Draw a beautiful self-similar fractal triangle.
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 was covered on Thursday (7/9). However, the material to complete the two programming questions (Boggle and the optional Voting problem) will be covered on Monday (7/13).
Practice with unit tests and debugging on core recursive functions.
Find all words on a given Boggle board and tally the maximum possible score.
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).
We provide a ZIP of the starter project. Download the zip, extract the files, and open the project in Qt creator.
The source files you will edit are
Additionally, you will answer questions in
Before getting started writing code, we highly recommend reading the CS106B Style Guide. All of your assignment submissions this quarter will be graded on their coding style, and this guide contains the coding standards that make up our style rubric.
Here are some resources that you might find helpful for this assignment:
- Trip's Assignment 3 YEAH Slides
- A Guide to Testing Code in CS106B
- Common Build/Run Errors Guide, put together by one of our wonderful section leaders, Jillian Tang.
- Stanford Libraries Documentation
- Lecture slides: Monday Intro to Recursion, Tuesday Recursive Fractals, Wednesday Using Recursion, Thursday Recursive Backtracking and Enumeration
- Section: 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 truly gifted educator.
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. You can contact us on Ed, email your section leader, or stop by the virtual LaIR (here is the schedule of help hours). You can find more information about how to get help at the LaIR here. As a reminder, try to visit the LaIR for coding debugging questions – however, if you cannot make it to the LaIR due to timezone issues, you can post on Ed to get help. However, you must use a private post if you are including code so that you are not posting your solutions for the whole class to see.
Before you call it done, run through our submission checklist to be sure all your ts are crossed and is dotted. Then upload your completed files for grading to the Paperless website.
Please submit only the files you edited; for this assignment, these files will be:
Note: When submitting to Paperless, due dates are expressed in PDT.