COS 126: Spring 1997Recursive Graphics Due: Wed. 3/26/97, 11:59pm

In this assignment, you'll use recursion to write a program that generates a program as output. Specifically, you'll write, in `htree.c`, a program that emits Postscript code to draw an "H-tree" pattern.

The H-tree is an example of a self-similar, or fractal, pattern that is defined using recursion. An H-tree with parameter r is defined by drawing an "H", and then recursively drawing four more H-trees with parameter r/2 at each of the four corners of the first H. The parameter r defines the thickness of the lines in the H. H-trees are of practical interest in designing microprocessor chips, because they're a good pattern to use for running the wires that connect circuit components when a tree of interconnections is needed.

`htree.c` should use a recursive function to draw an H-tree of size w with parameter r at (x,y), where w is the length of each of the three lines in an H and r is the thickness of each line. Here's pseudocode for the recursive algorithm:

if r > 0 then
put an H-tree with w = w/2 and r = r/2 at the upper left corner
put an H-tree with w = w/2 and r = r/2 at the upper right corner
put an H-tree with w = w/2 and r = r/2 at the left left corner
put an H-tree with w = w/2 and r = r/2 at the lower right corner
draw an H of size w at (x,y)

The basis case occurs when r = 0, at which point the recursive function does nothing. Although the H-tree pattern looks complex, the H-tree algorithm is very similar to the fractal star algorithm described on pp. 59 in Algorithms in C. Another, simpler, example is the recursive function for drawing a ruler described on pp. 54-57; code for this example is available in /u/cs126/examples/ruler.c.

You should write three functions:

 `htree` implements the algorithm described above; `draw` draws an H of size w with thickness r at (x,y); and `main` prints the header, calls `htree`, and prints the trailer

Your program will draw a pattern by emitting code in the Postscript page-description language. Writing programs that emit programs is a very powerful technique that has many applications. Most programs that produce graphical output emit Postscript, because Postcript is the language used to drive virtually all laser printers. It is a powerful, high-level, stack-based language designed specifically for rendering two-dimensional graphics and text. See the COS 111 Postscript "cheatsheet" for a quick introduction to Postscript. For more details than you'll probably ever need, see A First Guide to PostScript; this guide includes a concise summary of the Postscript operators. (Graphics freaks will want to buy a copy of the Postscript Language Reference Manual.)

Postscript coordinates are in units of "points" and the origin, (0,0), is at the bottom left of the page. There are 72 points per inch. For `htree.c`, we'll translate the origin to (50,50) and draw all output in a 512×512 integer coordinate system. To start, generate Postscript for drawing an H-tree centered at (256,256) with w = 256 and r = 2; your program should print the following Postscript.

```%!
50 50 translate 0.30 setgray
1 setlinewidth
64 384 moveto 128   0 rlineto stroke
64 320 moveto   0 128 rlineto stroke
192 320 moveto   0 128 rlineto stroke
1 setlinewidth
320 384 moveto 128   0 rlineto stroke
320 320 moveto   0 128 rlineto stroke
448 320 moveto   0 128 rlineto stroke
1 setlinewidth
64 128 moveto 128   0 rlineto stroke
64  64 moveto   0 128 rlineto stroke
192  64 moveto   0 128 rlineto stroke
1 setlinewidth
320 128 moveto 128   0 rlineto stroke
320  64 moveto   0 128 rlineto stroke
448  64 moveto   0 128 rlineto stroke
2 setlinewidth
128 256 moveto 256   0 rlineto stroke
128 128 moveto   0 256 rlineto stroke
384 128 moveto   0 256 rlineto stroke
showpage```

The first two lines are the header, and the last line is the trailer; use `printf` in your `main` function to emit these lines exactly as shown.

Each of the 4-line chunks that start with `setlinewidth` draw one H. The first four chunks draw 128-unit Hs with r = 1 at (128,384), (384,384), (128,128) and (384,128), and the fifth chunk draws a 256-unit H with r = 2 at (256,256). Use `setlinewidth` to set the thickness of the lines to r.

You can display the image specified in a Postscript file by sending it to a printer with the `lpr` command:

```% lcc htree.c
% a.out | lpr```

Make sure your output starts with the header shown above; if the first line of the output is not "`%!`", you'll get just the Postscript code instead of the image. And if you forget the "`showpage`" trailer, you'll get a blank page.You can also use `gs`, the Ghostscript previewer, to view Postscript. Redirect your Postscript output to a file, then run `gs` on the file:

```% a.out >foo.ps
% gs foo.ps```

Once you can draw the r = 2 pattern, revise your program to draw the r = 32 pattern shown here, and turn in this version of `htree.c`. (It's easyand convenientto have your program accept an optional argument that specifies r, so that, for example, the command "`a.out 2`" draws the r = 2 pattern. This feature is not required, however.)

`/u/cs126/bin/submit 6 readme htree.c`

### Extra Credit

Postscript is a complete programming language with variables, procedures, control structures, and so on. Write the H-tree program completely in Postscript and submit it as `H-tree.ps`. Use this file name to avoid confusing your Postscript program with the output from `htree.c`.

### More Extra Credit!

Do another, different, recursive design. Experiment with implementing a different `draw` function or a different `htree` function. For example, on page 59 of Algorithms in C, `star` calls `box`, which uses `fill` to fill the boxes with white. Calling `draw` or `box` at different points with respect to the recursive calls will produce different and interesting effects. Try Xs or Ss instead of Hs, or use recursive triangles, or whatever. You might try introducing some randomness. For example, change the pattern between recursive calls. If there's sufficient interest, we'll hold a class vote for the best design from 5 "finalists" and plaster it on the back of the COS 126 T-shirts.

If you do the extra credit, submit your design as `graphic.c`.

References
R. Sedgewick, Algorithms in C, 2nd ed., Addison-Wesley, 1990, pp. 51-59.