Assign3: Recursive Problem Solving

Due Thursday, July 15 at 11:59 pm

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.

Learning goals

After completing this assignment, you will be able to


Assignment parts

This assignment consists of a collection of multiple different recursive exercises, grouped into two parts.

Getting started

We provide a ZIP of the starter project. Download the zip, extract the files, and open the project in Qt creator.

📩 Starter code

The source files you will edit are fundamentalwarmup.cpp, balanced.cpp, sierpinksi.cpp, merge.cpp, backtrackingwarmup.cpp, and boggle.cpp.

Additionally, you will answer questions in short_answer.txt.

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.

Helpful Resources

Here are some resources that you might find helpful for this assignment:

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. 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.

Submit

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:

🏁 Submit to Paperless

Note: When submitting to Paperless, due dates are expressed in PDT.