Recursive and Iterative Processes in Quilts

David Wolfe

February 26, 1999

I see three important ideas worth emphasizing in the quilting project report: (a) making complex patterns on the computer, (b) recursive and iterative processes, and (c) using small building blocks to build complex structures.  I recommend choosing one to emphasize in your introduction, and then structuring your report around that choice.  I chose (b) (for no especially good reason.)

Testing, although short, was descriptive of the actual testing I did.  By reading it, you are more likely to be convinced of just how thorough the testing is than if either (a) the tests were all explicitly included verbatim, or if (b) a statement is made that all procedures were, ``thoroughly tested''.

0 Introduction

Iteration and recursion are two powerful techniques for generating complex processes.  Recursion is used to delegate smaller tasks in the hopes of solving a larger task.  Iteration is used to convert a complex task into a simpler one.

In this report, we'll investigate these techniques in the context of building large quilt patterns from simple primitives. Section 1 will introduce the primitives used to make images on a computer screen. (Most of their definitions appear in the Appendix.)   Sections 2 and 3 form the core of the report, describing iterative and recursive approaches to building large rectangular repeating quilt patterns.  This will be followed by brief sections on testing and concluding remarks.

1 Basic Primitives

As in all programming tasks, some operations are treated as primitives.  In this report, we treat the following procedures as primitive, even though they are not built-in Scheme procedures.

(quarter-turn-right image)      Turn an image 90 degrees clockwise
(quarter-turn-left image)       Turn an image 90 degrees counter-clockwise
(half-turn image)               Turn an image 180 degrees
(invert image)                  Reverse colors - black and white
(stack top-image bottom-image)  Stacks an image on top of another image
(side-by-side left-image right-image)  Places two images side by side
The definitions for these procedures appear in the Appendix of this report, as these definitions are not strongly relevant to the theme of the report.

2 Recursion and Induction

Using these primitives, we wish to construct rectangular blocks of images.  Constructing, say, a 2 x 2 image using the primitive procedures is easy.  However, to write a single procedure which displays an m x n array of images for any values of m and n, we'll need to use recursion and/or iteration.  In this section, we'll try both and compare the two.

The program separates the task of building a stack of images h high from that of putting together w images side by side.  Each of these tasks is simpler than trying to build a w x h quilt straight-away.

Recall that a recursive program breaks a problem down into one or more smaller problems, and uses the solutions to those to solve the original.  A recursive program to build a stack h high can recursively make a stack h-1 high, and then tack on the h-th image:

An iterative process converts a problem to a simpler one.  Here, we'll convert the problem of stacking n images to one of stacking n-1 additional images on top of one.  To do this, we'll stack n-2 additional images on top of two.  And so forth.  The procedure is shown below:

3. Quilts and checkerboards

An mxn quilt is simply replicates the same image in an mxn grid. In a "checkerboard" the image is inverted in every other position. Both can be made using recursion or iteration. Specifically, the procedure quilt below works by …

4 Testing

Each procedure was tested on appropriate arguments.  For an integer argument, I methodically tried 1, 2 and 3.  For an image argument, I always used a basic block which was asymmetric to be sure that it was properly rotated.  For side-by-side, I was sure to use two different images to verify the left image ended up on the left.  For procedures like quilt, I tried arguments with different width from height to be sure to get rectangles oriented properly.

The procedures make no checks for illegal arguments such as non-integers, non-positive integers or non-images.

You may display a few images from DrScheme to illustrate your testing of your code. However do not just attach a printout of all images from the project.

5 Conclusion

Recursion and iteration can each be used to generate complex behavior from simpler primitives.  These techniques form the foundation of complex programs for graphical manipulation (as we saw here), for numerical calculations which might be more familiar, or perhaps, for other applications I have yet to see. 

A Appendix: Primitive Procedures I Defined and Definition of Pinwheel

In general, an Appendix can be used to provide the definitions of any procedures which were required by the assignment but which do not fit into your report in any natural way. These would include the definitions for side-by-side, half-turn, and the like.