Lab 3: What Does Recursion Look Like?

Intermediate Student

(require 2htdp/image)

This week, you will practice writing recursive functions to produce a series of increasingly complex images. These designs will allow you to see recursion in action. As you will see, it's amazing how much complexity can arise from the repeated application of just a few simple rules.

A Classic

Today's exercise builds towards reproducing a figure from Abelson and Sussman's seminal text Structure and Interpretation of Computer Programs ("SICP").

This is not the actual figure from that text, but its construction is fundamentally the same.

To test all your functions today, use the following image as your building block. It is included in the lab 3 starter code. You can produce it by evaluating (design 64).

Download lab3-starter.rkt and open it in DrRacket.

Proceed by writing the functions specified below. In doing so you will build the skills -- and a toolkit -- to reproduce the figure above. For this exercise, nothing in 2htdp/image is off-limits. Use scale, beside, above and whatever else you find apt for the task at hand.

;; quarter : img -> img

The function quarter should consume a square image and produce one whose side length is half as long. (The image produced has one quarter the area of the image consumed.)

;; row : num img -> img

The function row should produce a row of n images. For example, (row 4 (design 64)) should produce this:

;; col : num img -> img

The function col should produce a column of n images. For example, (col 3 (design 64)) should produce this:

;; grid : num num img -> img

The function grid should produce a grid of images of the given dimensions. The first argument is the grid width, the second is the height. For example, (grid 5 2 (design 64)) should produce this:

;; shrinking-row : img -> img

The function shrinking-row should produce a row of images with the following property: the original image (the one given as an argument) should be scaled down to 3/4 its original size at every step. For example, (shrinking-row (design 64)) should produce this:

;; bsr : img -> img

bsr stands for "bidirectional shrinking row" (for lack of a better name). It's better explained as picture than in words. (bsr (design 64)) should produce this:

Again, the images are scaled 3/4 at every step.

;; sicp : img -> img

(sicp (design 128)) should produce this:

The pattern is full of self-similarities and mirrorings. Exploit them by writing auxiliary functions to assist in its construction.

There are suggestions for some fun enhancements at the bottom of the starter file. Have a look! (No extra credit.)

Good luck, everyone. As usual, you will be evaluated not only on correctness of your final results, but also on proper documentation, including contracts and purposes for all functions, style (judicious code factoring and no spaghetti code), and ample tests.

Submit

Submit your work via CS151 Handin by 10 PM on Sunday Oct 17. Make sure your work is submitted as Lab3.

Errata

10/14/2010: two edits to fix misstated examples above. (col 4 ...) was corrected to (col 3 ...), and (sicp (design 64)) to (sicp (design 128)). Thanks to the sharp-eyed students who noticed.