Assignment 3. Recursion


Due Friday, April 23 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 48 hours after the due date. Late submissions are accepted during the grace period with no penalty.
  • The grace period expires Sun, Apr 25 at 11:59 pm Pacific, after which we cannot accept further late submissions.
  • 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 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 can be completed individually, or in pairs. What does this mean (please read carefully!):

  • Pair Programming (see this link) has a long history, and has been shown to be an effective programming tool for effective coding.
  • You are allowed to work with one other person currently in CS106B. They can be in your section or in another section.
  • You must work on the assignment 100% together. This means:
    • You are never allowed to work on any part of the assignment alone, aside from reading the assignment specifications.
    • Both partners must work on all parts of the assignment together. If we have reason to believe that partners "split" the assignment and wrote the parts individually, or did not work on the assignment together, we will assign a 0 for the entire assignment to both partners, and we will refer both students to the Office of Community Standards for an honor code violation.
    • If you attend LaIR or office hours, you must do so with your partner.
    • Partners should switch between typing the code. E.g., one partner can be typing the code while the other is discussing what to type. Pair-programming is always a joint effort.
    • If one partner is more advanced, that partner has a duty to ensure that the other partner understands every line of code that is written, and the pair should discuss each line of code in enough depth to ensure that both partners fully understand the code.
  • Partners will still have individual grading sessions (IGs) with their Section Leaders. SLs will expect that each student can discuss their code in depth, assuming that both partners understand all the code that was written.
  • If you work with a partner for this assignment, you must either work with the same partner for any future pair assignments in the class, or work alone (this is because grading for pair assignments is logistically difficult, so we cannot allow pair switching).
  • Both students will individually submit their identical assignments, and the names of the pair (and SUNets) must be on the first line (in a comment) for any file you turn in.
  • If you have any questions, please post a question on Ed, or ask in LaIR or Office Hours.

Learning goals

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.

Assignment parts

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

  • Warmup

    Practice with unit tests and debugging on recursive functions.

  • Balanced

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

  • Karel GPS

    Help Karel find the way home by counting possible routes to the origin.

  • Sierpinski Fractal

    Draw a beautiful self-similar fractal triangle.

  • Merging Sorted Sequences

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

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 are warmup.cpp, balanced.cpp, karel.cpp, sierpinksi.cpp, and merge.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. You can contact us on Ed, email your section leader, stop in to office hours or get one-on-one help at the virtual LaIR. 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 submit checklist to be sure all your t's are crossed and i's dotted. Then upload your completed files to Paperless for grading.

Please submit only the files you edited; for this assignment, these files will be:

  • warmup.cpp
  • balanced.cpp
  • karel.cpp
  • sierpinksi.cpp
  • merge.cpp
  • short_answer.txt

Remember: if you are in a pair, put both students' names and SUNets as a comment in the first line, e.g.,

// Pair: Chris Gregg (cgregg) and Chase Davis (chased)

🏁 Submit to Paperless

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