Assign3: Recursion

Due Friday, May 01 at 11:59 pm

• The assignment deadline is by the end of the day, Anywhere on Earth.
• Submit by end of day Friday deadline for a small, “early-bird” bonus.
• All students have a pre-approved extension or "grace period" that extends until Sunday end of day AoE, with no penalty.
• The grace period expires end of day Sunday, after which we cannot accept further late submissions.
• Note that our Paperless submission system displays due dates and submission times in PDT frame of reference.

This week's assignment is a recursion "sampler", focusing on implementing a number of small, isolated recursive functions. 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!

The recursive solutions you need to write are quite short; just a handful of lines each. However, this doesn't mean you should put the assignment off until the last minute! It may only take a few concise, elegant lines, but recursive code can be dense and complex and requires your full attention to get the details just right.

Recursive problem-solving also can take a bit of time to get used to. We recommend that you start on the problem set early in the week, so as to allow yourself enough time to wrap your head around this new way of solving problems.

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.

Learning goals

• To be introduced to the delight and elegance of recursive problem-solving
• To learn the process of recursive decomposition, dividing a problem into base case(s) and recursive case(s)
• To learn 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.

• Combinations

  Count mathematical combinations, i.e. the number of ways to choose K things from a set of size N.

• Sierpinski Fractal

  Draw a beautiful self-similar fractal triangle.

• Text predict

  Predict a user's intended word when typed on old-style phone keypad.

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 warmup.cpp, balanced.cpp, combos.cpp, fractal.cpp, and predict.cpp.

Additionally, you will answer questions in short_answer.txt.

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

Getting help

Here are some resources that you might find helpful while working on this assignment:

• Assignment 3 YEAH (Your Early Assignment Help) Session. This is an introductory session for the assignment led by a section leader that is meant to help you get started and equipped with the knowledge you need to successfully complete the assignment. The A3 YEAH Session will take place on Monday, April 27 from 5:30-6:30pm PDT. Zoom information can be found here. The session will be recorded and posted on Canvas. Slides from the session can be found here.
• Lecture Slides: Wednesday Recursion, Friday Fractals, Monday Procedural Recursion
• Section: Recursion
• Textbook Chapters 7 and 8. 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.
• We’re here to help you get there! Contact us on Ed discussion, email your section leader, or come join non-stop coding party that is the LaiR.

Submit

Review our submission checklist before calling it done. Upload your completed files for grading to the Paperless website.

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

• balanced.cpp
• combos.cpp
• fractal.cpp
• predict.cpp
• short_answer.txt

🏁 Submit to Paperless

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