Recursion Etudes

Due Wednesday, July 17 at 11:59 PM

• Submit to Paperless. Deadline is 11:59 PM.
• The late day policy gives you the ability to self-grant an extension (as long as you have not used all your late days); we trust you will make reasonable and sparing use of this power. Be sure to reserve late days for emergencies.
• Reminder: You have a limited pool of late days. You have a total of 4 late days to use throughout the quarter, but you cannot use more than 2 late days per assignment. Late days are expended in 24-hour blocks. See the Assignments page for more details.

---

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 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 without delay. Read over the problem statements and get your brain starting to mull it over. There is not a large amount of code to write, but you want to give yourself 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 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 architect recursive solutions for ever more impressive problems.

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…

• Develop the recursive insight to decompose a problem into smaller, self-similar tasks.
• Structure a recursive solution 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, debugging, and analyzing recursive functions.

Assignment parts

This assignment consists of a short warmup exercise and four recursive functions.

• Warmup

  Practice with unit tests and debugging and timing recursive functions.

• Balanced

  Determine whether an expression has properly matched pairs of bracketing operators.

• Sierpinski Fractal

  Draw a beautiful self-similar fractal triangle.

• Ballot counting

  How likely to have no change in leader when tallying ballots?

• Merging Sorted Sequences

  Implement an efficient divide-and-conquer algorithm for merging sorted sequences.

Getting started

📦 Starter project

The starter project is provided as a zip archive. Download the zip, extract the files, and move the project folder to your CS106B folder. Open the .pro file in Qt Creator to get started.

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.
• Textbook Chapters 7 and 8. These chapters are a great resource —the explanations and examples for recursion are Professor Eric Roberts at his very best. Eric is our long-time Stanford colleague and a gifted educator.
• Eric also wrote a lovely full book Thinking Recursively, available in Stanford library https://searchworks.stanford.edu/view/1194923

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. We welcome your questions on the Ed forum. Always start by searching first to see if your question has already been 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 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:

• ballots.cpp
• balanced.cpp
• sierpinski.cpp
• merge.cpp
• short_answer.txt

🏁 Submit to Paperless

Note: On Paperless, all due dates and submission times are expressed in Pacific time.