Chapter: Recursion and Fractals

The term fractal was coined in 1972 by Benoit Mandelbrot. It refers to shapes that, when you magnify any part, you obtain another shape that is very similar to the original. You generated some well-known fractal curves in Lab 10.

Fractals abound in nature. Think of a coastline. These four pictures were all obtained from satellite images provided by google maps. They are at vastly different scales. One is at a scale of hundreds of miles per inch. Another is mere feet to the inch. There are some clues as to which is which, but these are provided mostly by limitations in the image resolution and in the screen resolution. If we had unlimited resolution (as, essentially, we do once we abandon our satellites, our cameras, our computers and other technological impediments, and relied on our natural senses) it would be very hard for us to distinguish which of the pictures is at which resolution.

Recursive programming is used in computer graphics to try to simulate nature. The wikipedia timeline of the use of CGI (computer graphics) in movies indicates the effective use of fractal techniques in Star Trek II The Wrath of Khan as long ago as 1982. Below, there are two pictures of trees: One is of a real tree, the other is of a "tree" generated from an L-system. Can you tell which is which? Wikipedia has a good explanation of Lindenmeyer systems.

Below is an applet developed by Kim Bruce and Andrea Danyluk, to which I have added a start button. It draws "parsley", and then lets you move the parsley plant around with the mouse.

        
             
            Your browser is ignoring the <APPLET> tag!      
        

Here is the code for the applet. Nothing new nor unexpected. You should be able to write such code in your sleep by now! Note that the important feature is the call to new ParsleyTree(new Location(200,300), 150.0, Math.PI/2.0, canvas);

What is a ParsleyTree? Well, if you watch the construction carefully, just as you watched the Tower of Hanoi animation, you should be able to spot the recursion. A ParsleyTree consists of

• a stem,
• and three more smaller ParsleyTrees

At least that is so until the ParsleyTrees get below a certain minimum size. At which point the recursion terminates. That is our base case.

Q. 1

Does nature have a base case?

Here is Java code for ParsleyTree. Load it and the previous LivingParsley into BlueJ and make sure it works. Make small adjustments to the values in the static final double constants until you like the look of your parsley.

Exercise 1

Very similar to the parsley is this Broccoli applet (mostly due to Kim Bruce but with minor changes by me):

        
             
            Your browser is ignoring the <APPLET> tag!      
        

Watch it and see if you can spot the recursion and what you need to do. One thing is that the base case involves actually doing something (placing that yellow flower).

Exercise 2