Part 0:   Preparation

Read the Notes on Recursion, especially the section on recursive graphics.


Part 1:   H-tree pattern

  • Here are two good warmups programs which can be done independently:

  • Write a (nonrecursive) function void showH(void) that prints the moveto and rlineto (or lineto) commands needed to draw only one large H. Write your main function so that it prints out the PostScript header information, then calls showH, then prints out the final showpage command. This will give you confidence that your program is producing valid PostScript.

    As a second step, expand your showH() function so that it now takes three arguments x, y, and size of type double. Write your function so that it draws an H, centered at PostScript coordinate (x,y), and with each of the 3 line segments having length size. You will probably want to use exactly this showH() function in your final program. To debug and test your function, modify main() so that it calls showH() a few times, with different parameters.

  • Write a recursive function recur() that takes one int argument n, prints the value n, and then calls itself four times with the value n-1. The recursion should stop when n becomes 0. To test this function out, write main() so that it reads one integer n from standard input using scanf(), and calls recur() with that value. You should get the following output. Make sure you understand how this function works, and why it prints the numbers in the order it does.

    As second step, modify recur() so that instead of printing n, it prints the size of the H to be plotted. The first call to recur() is from main(), and it plots the big H. Each line segment of the big H has length 256.0, so print 256.0. Each successive level of recursion will halve the length. Your function should produce the following output.

  • Once you feel a little comfort with recursion and PostScript, try to figure out how to print the recursive H pattern. Start by drawing H's with pencil and paper. Do some calculations to figure out the geometry of where the smaller H's should go. Part of the challenge will be figuring out what information you need to pass to the recursive function. At the very least, it will need to know where to plot the H, and how big it should be.

  • Do not be alarmed if your PostScript output does not exactly match the PostScript output given in the course packet: it will depend on the order in which you make the recursive calls. However, you should get exactly the same picture. Also, feel free to use the lineto command instead of rlineto if you are more comfortable with a fixed coordinate system.

  • After you compile your program, type "a.out > htree3.ps" and then type 3 and hit enter. You can then view the PostScript program with:
    gs htree3.ps
    
    If you get an error when trying to view, then your probably made a mistake with the PostScript syntax. Input a small value for n to help find the error.



  • Kevin Wayne