Assignment 3. Recursion Adventures

This assignment was designed by Julie Zelenski

Due Wednesday, July 26 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 Thu, Jul 27 at 11:59 pm Pacific, after which we will deduct 15% per late day.
  • You must submit the assignment by Tue, Aug 1 at 11:59 pm Pacific to receive any credit. We will not accept any submissions past this date.
  • 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.

Recursion is a powerful problem-solving tool with many practical applications. This assignment is a recursion "sampler" that introduces recursive problem-solving through several independent programs. We'll begin with Part 1: Fundamental Recursion. Part 2: Recursive Backtracking will draw from week 4's lectures and will be released on Wednesday, July 19th.

Most students find that it takes some time to get comfortable thinking recursively, so we recommend that you start the assignment early. Even though you'll have more than a week after the midterm to complete this assignment, Part 1 could be a great study resource, as recursion will be on the exam. Read over the problem statements early and get your brain starting to mull them over.

There is not a large amount of code for you to write for Part 1, 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. By next week, you'll be in prime shape to tackle recursive solutions for even more impressive problems, when Part 2 is released.

This assignment is to be completed individually. Working in pairs/groups is not permitted.

Learning goals

After completing Part 1 of the 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.

After completing Part 2 of the 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
  • Apply the choose/explore/unchoose pattern of recursive backtracking to explore all possibilities throughout a search space
  • 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. These problems will serve as the foundational practice for you to begin to grapple with the core tenets of recursive problem-solving.

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. We will release this part of the assignment on Wednesday, July 19th.

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 for Part 1 are sierpinski.cpp and merge.cpp.

The source files you will edit for Part 2 are predict.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:

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

  • short_answer.txt
  • sierpinski.cpp
  • merge.cpp
  • predict.cpp
  • boggle.cpp

šŸ Submit to Paperless

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