Assignment 3: Recursion
Assignment by Chris Gregg, based on an assignment by Chris Piech, Marty Stepp and Victoria Kirst. Originally based on a problem by Julie Zelenski and Jerry Cain.
Screenshots from the Mandelbrot and Grammar Solver parts of the assignment.
This assignment focuses on some cool problems that can be solved with recursion, both graphical (fractals) and textual (grammar solver). In the first portion of the assignment, you'll write several recursive functions to draw graphical patterns, also known as fractals. In the second portion of the assignment, you'll write a function to generate random sentences from provided "grammars", or word structures. This lets you generate random text, but from only the syntax rules, and not any previously-written text. We hope you enjoy these problems!
This assignment consists of two parts:
Each part can be programmed separately, but they should be submitted together. The starter code for this project is available as a ZIP archive (this contains 2 separate QT projects, one for each part of this assignment):
Demo JAR
Note: ignore 20 Questions and Fractals flood fill. Also, the JAR does not demonstrate Mandelbrot.
It is fine to write "helper" functions to assist you in implementing the recursive algorithms for any part of the assignment. Some parts of the assignment essentially require a helper to implement them properly. However, it is up to you to decide which parts should have a helper, what parameter(s) (if any) the helpers should accept, and so on. You can declare function prototypes for any such helper functions near the top of your .cpp file. (Don't modify the provided .h files to add your prototypes; put them in your own .cpp file.) We provide a GUI (graphical user interface) for you that will help you run and test your code.
Turn in only the following files via the Paperless submitter:
fractals.cpp, the C++ code for the Part A Fractals programgrammersolver.cpp, the C++ code for the Part B Grammar Solver programmygrammar.txt, your own unique Part B input file representing a grammar to read in as your program's input
YEAH (Your Early Assignment Help) Resources
The slides can be found here, and in the "YEAH" dropdown above. The video is available on the lecture videos page.Pair Programming
You may optionally work on this assignment as a pair programming assignment.
If you would like to work in a pair on this assignment, you may, under the following
conditions:
- Both partners must be in the same section (time and location).
- At no time should partners be coding alone. To be clear: all coding must be done together, on a single computer. One partner should type, and the other should watch over that partner's shoulder. Each partner should take turns at the keyboard.
- When you go to the LaIR or office hours for help on your assignment, both students must be present in the pair to receive help. Only one partner should sign up for help in the LaIR Queue at a time.
- Pair programming is less about sharing the workload and more about sharing ideas and working together. During the IG for the assignment, if a Section Leader does not think both partners contributed equally and worked together, the SL may forbid pair programming on a future assignment.
- Pairs who "split the assignment" where one partner does part of the assignment alone, and the other partner does another part of the assignment alone, will be in violation of the Honor Code.
Style Details
As in other assignments, you should follow our Style Guide for information about expected coding style. You are also expected to follow all of the general style constraints emphasized in the Homework 1 and 2 specs, such as those detailing good problem decomposition, parameters, using proper C++ idioms, and commenting. The following are additional points of emphasis and style constraints specific to this problem.
Recursion: Recursion: Part of your grade will come from appropriately using recursion to implement your algorithm, as we have described. We will also grade on the elegance of your recursive algorithm; don't create special cases in your recursive code if they are not necessary. Avoid "arm's length" recursion, which is where the true base case is not found and unnecessary code or logic is inserted into the recursive case. Redundancy in recursive code is another major grading focus; avoid repeated logic as much as possible. As we mentioned above, it is fine (and sometimes necessary) to use "helper" functions to assist you in implementing the recursive algorithms for any part of the assignment.
Variables:
While not new to this assignment, we want to stress that you should not make any global or static variables (unless they are constants declared with the const keyword). Do not use global variables as a way of getting around proper recursion and parameter-passing on this assignment.
Collections: Do not use any collections on any graphical algorithms in this part of the assignment.