Recursion in Nature, Mathematics and Art Anne M. Burns Department of Mathematics Long Island University C.W. Post Campus Brookville, NY 11548
Abstract This paper illustrates a number of ways that recursion and replacement rules can be used to create aesthetically pleasing computer generated pictures. Starting with imitation of forms found in nature, we move to more abstract designs, first designs derived from the nature imitations, and finally a purely abstract example. 1. Introduction "In order to understand recursion, one must first understand recursion", from Wikipedia, the free encyclopedia Many of the forms and shapes found in nature exhibit some form of self-similarity; the larger form appears to contain smaller copies of itself at different scales. Examples abound in the plant world; we see it also in mountains, clouds, the branching structure of rivers and blood vessels, patterns on animal skins, etc. Nature imposes restrictions on growth rules, but that doesn’t mean that the artist needs to. First imitating the forms and shapes in nature, the artist finds herself changing a shape, a scale or a color to produce a more abstract but visually appealing picture. We will start with algorithms that produce imitations of forms found in nature; next we combine them into what a colleague of mine termed "Mathscapes", and finally we will abstract the forms into visually appealing designs. In mathematics and computer science a recursive function is a function that calls itself; by calling itself more than once a function can produce multiple copies of itself. This makes it an excellent technique for creating figures which are defined by "replacement" rules. Consider the following examples of replacement rules: In each of Figures
1 and 2, start with the leftmost figure. Then replace it by the second figure. This gives you the replacement rule. For example, in
Figure 1 start with a line segment. At step 2 replace the line segment with 5 line segments as pictured, each 1/3 the length of the original. At step
In Figure 3 the replacement rule is a little different; it is an example of a
2. Imitating forms found in nature
Figure 6 shows the compounding of some of the inflorescences. These pictures were all done with simple recursion.
monochasium dichasium umbel panicle
Figure 7 shows some imaginary inflorescences obtained by using random numbers to vary segment lengths and angles and taking artistic liberties with the above. .
Another model for plants can be found in the article by deReffye et al [6]. In this model at each stage of growth a "bud" can do one of three things: (1) branch, (2) flower and ultimately die or (3) sleep (do nothing until the next stage). A probability is assigned to each of the three outcomes, such that the probabilities add up to 1. We start with a single bud; at each stage, for each bud that is still alive, we generate a random number between 0 and 1; the number determines the next state of that bud. For added realism we can make the probabilities functions of time, so that at later stages the probability of a bud dying is higher. Figure 8 shows three imaginary "trees" using a branching number of 2, that is, when a node branches it produces two new branches. The exact same program drew the three trees; using probabilities and random numbers we can make it look as if the three trees come from the same family, but are not identical.
Another of my favorite ways to model botanical growth is a method called L-systems, or string rewriting. It was discovered by Aristid Lindenmayer, a Dutch biologist who had the remarkable idea of using concepts from formal language theory to describe plant growth, and developed by Premislaw Prusinciewicz [9]. In this model each geometric part of the plant is assigned a character. Here is a simple example: let I represent an internode, L a leaf and F a flower. We use brackets and parentheses to indicate branches. Square brackets enclose a branch to the left, parentheses enclose a branch to the right. For example, the string of characters I[I[L](L)IF]I(II(L)IF)IF might represent the imaginary plant in Figure 9a. At each stage we use a set of rewriting rules (productions) to successively replace each character by a string of characters. Figure 9 illustrates several stages in the development of an imaginary plant using this method.
Another method of modeling plant growth and other branching phenomena uses a stochastic matrix of probabilities; this method is reminiscent of a Markov chain. Space considerations preclude a description here, but the interested reader can find more in [5].
First we outline the recursive midpoint algorithm for generating the height field. We start with a 2 Once the height field is generated we can render it as three dimensional mountains using some calculus and trigonometry, illustrated in Figure 11a, or we can assign a continuous ramp of colors to the heights and render it as clouds, illustrated in Figure 11b. By changing the scale factor that we use in scaling down the random amount that we add at each stage, we can produce sharp fractal-like mountains and clouds or soft rounded mountains and cumulus clouds. Figure 10a Figure 10b Figure 10c Figure 10d Can you guess which pixels will be assigned at Stage 5?
Soft, rounded mountains, like those found in Vermont, can also be produced by using sums of trigonometric functions with randomly assigned coefficients, which can then be projected onto a two-dimensional picture using the same rendering technique that we used for the fractal mountains generated by the midpoint algorithm. In Figure 12, "Mathscape", I have combined the recursive algorithms for clouds, mountains and various imaginary plant forms into one picture.
4. "Persian" Rugs The midpoint algorithm that produced the clouds and mountains can also be used to generate abstract designs that resemble Persian rugs. Instead of adding a random amount at each stage, we add an integer amount based on some function of the previously assigned values. Then to each integer we assign a color. For example, in the first stage of the recursion we assigned a value to the middle point based on the values assigned to the corner points. To design a "Persian" rug, since we want symmetry, we would initially assign the same integer value to the four corner points. To get the value for the center point we let
5. Using recursion to produce abstract designs Looking at the replacement rule illustrated in
Figure 2 we see that it seems to say: start with a circle, replace the circle with four smaller circles tangent to each other and tangent to the original circle. Then at the next stage repeat the operation with each of the new circles. We can generalize this procedure using what mathematicians call an Function If (step == 0){ Draw the circle with center } else{ for ( find } } } The limit set of an IFS is the set of points that is invariant under all compositions of the contraction mappings. In general it is a fractal. For a complete theory see [1]. To produce interesting designs, we can just carry out the recursion for a few steps. For iterated function systems involving circles it is convenient to use Möbius transformations which map circles to circles.
If we carry out the recursion suggested by Figure 2, we find that the design is not particularly interesting. The transformations that take the original circle into the four smaller circles are affine transformations; they shrink and then translate the original circle, but do not distort it. We can generate more varied pictures if we alter the original transformations by composing them with Möbius transformations from the unit circle group. Transformations from the unit circle group map the unit circle to itself, expanding it or contracting distances along the circle depending on two complex parameters. As we iterate the distortions propagate, producing more varied and interesting designs. In Figure 14 we see the effect of changing the parameters. We have also added to the replacement rules a central circle that is tangent to the other four and in the rightmost picture we have increased the number of circles tangent to the original circle to six. Figure 15 shows two renderings where we increase the number of circles to thirteen, show only selected stages of the recursion and use color in imaginative ways.
References [1] M. Barnsley, [2] A. Burns, " [3] A. Burns, "Recursion: Real and Imaginary Inflorescences", [4] A. Burns, " ‘Persian’ Recursion", [5] A. Burns, "Modeling Trees with Stochastic Matrices", [6] P. deReffye, C. Edelin, J. Francon, M. Jaeger, C. Puech, "Plant Models Faithful to Botanical Structure and Development", [7] D. Mumford, C. Series and D. Wright, [8] C.L. Porter, [9] P. Prusinkiewicz and A. Lindenmayer, |