Write a program that can create an H-tree pattern, on the back of this page. Then develop a program that prints recursive patterns of your own design. The H-tree is another example of a fractal pattern like the Mandelbrot set. It also of practical interest in circuit design. For example, imagine that we want to lay out circuit components on a microprocessor chip so that the length of wire connecting each component to the clock is the same. (This property is desirable to achieve uniform wiring delays.) The H-tree pattern gives a practical solution: position the clock in the center of the biggest H, and put each circuit component at one of the exposed endpoints of the smallest H's.

Part 1.   Though the H-tree pattern looks complex, it can be generated with a recursive program very similar (in fact, identical!) to the one that draws the pattern in Figure 5.12 in Algorithms in C. Your task is to make a file htree.c with a recursive function and a main() driver that will call the recursive program once and output a turtle graphics program (in the manner to which we have become accustomed) to produce the desired effect. Think recursively: write a program that draws an H and calls itself 4 times (and includes a termination condition).

Your program will read in an integer n using scanf() that controls the depth of the recursion. First, make sure that your program can draw a single H, with n set to 1. Then, check that it works for 2 levels of recursion (draws five H's). That is, your program should produce the following turtle graphics output when n is 2.

% echo 2 | htree F 128.00 256.00 D 256.00 F 128.00 128.00 R 90 D 256.00 R -90 F 384.00 128.00 R 90 D 256.00 R -90 F 64.00 384.00 D 128.00 F 64.00 320.00 R 90 D 128.00 R -90 F 192.00 320.00 R 90 D 128.00 R -90 F 320.00 384.00 D 128.00 F 320.00 320.00 R 90 D 128.00 R -90 F 448.00 320.00 R 90 D 128.00 R -90 F 64.00 128.00 D 128.00 F 64.00 64.00 R 90 D 128.00 R -90 F 192.00 64.00 R 90 D 128.00 R -90 F 320.00 128.00 D 128.00 F 320.00 64.00 R 90 D 128.00 R -90 F 448.00 64.00 R 90 D 128.00 R -90

Your program will be nearly (or completely) debugged when you get to this point. Check that it works with n set to 6.

Part 2.   In this part you will create your own recursive design. First, do something different for your basic graphic design. For example, you can have the regions represented by the recursive calls be rectangles of varying size, or you can have them overlap. Or, work with X's or S's instead of H's. Or, use the spot command to produce filled squares. Or, use five recursive calls and pentagons, or whatever. Try using color or introducing some randomness. Originality and creativity in the design will be a factor in your grade.

Submission.   Submit the files: htree.c, art.c, input1.txt, input2.txt, and readme.txt file. The two input files should contain the input data with which you want us to run your art.c program.

Extra Credit.   Write a program to make the recursive H pattern using a non-recursive and bottom-up method like Sedgewick Program 5.9. Or, write a recursive PostScript program to produce your pattern.