From Curran Kelleher, "Recursive Structures and Processes," MIT Open Courseware (24 Aug. 2007) 10-12.
1.2.7 Iterated Function Systems [= "a method of constructing fractals; the resulting constructions are always self-similar" (wikipedia)]
Iterated Function Systems (IFS) take a single point and move it around repeatedly, plotting a point on the screen for each move. The point is moved according to a mapping function, which is chosen probabalistically from several possible mapping functions.
["The fractal is made up of the union ['collage'] of several copies of itself, each copy being transformed by a function (hence 'function system'). . . . The functions are normally contractive. . . . Hence the shape of an IFS fractal is made up of several possibly-overlapping smaller copies of itself, each of which is also made up of copies of itself" (wikipedia).]
[Barnsley's fern, cf. Michael Barnsley, Fractals Everywhere (Academic P, 1988)]
The fern IFS is a system of four mapping functions. Each of these functions is a mapping from the outermost rectangle to another, smaller rectangle. The system is comprised of the following four functions, which map from any point inside the outermost black rectangle . . .
1. to a point on the green part of the stem (1% of the time)
2. to a point in the red rectangle, the lowest left branch (7% of the time)
3. to a point in the dark blue rectangle, the lowest right branch (7% of the time)
4. to a point in the light blue rectangle, which spirals everything upwards and smaller (85% of the time)
Figure 1.1: The rectangles used in the coordinate transformations (approximately), and the image generated by our program.
Here is Java code which implements this IFS:
Is this algorithm recursive? The code itself is not recursive, it is just repetitive. However, the mappings are recursive, because they are applied to themselves eventually. The ﬁlling in of the fractal object happens because of the randomness introduced by selecting probabilistically which of the four mappings to apply.