Logo

Recursions

Observing objects or states of the world usually implies to look at these objects or states at certain moments in time. To observe the size of a swarm of fishes or a flock of birds for instance provides information about these sizes in distinct moments of time. To observe the change of these sizes usually involves more than one observation, since observing continuously is difficult. Especially in the context of science, observations are usually interrupted by activities like documenting and analyzing the observed data. In most cases hence, there will be time between observations. One might count the number of fish in a swarm just once in a year for instance, and then come back a year later to report changes. Observational data hence is usually gained in discrete time steps. The mathematical method to report and calculate changes in such data is called difference equation, and has the following form:

St+1 = St + gain

with S denoting the stock of the observed, i.e. the size of the swarm for instance, t denoting the time of observation, and gain indicating the amount about which the stock has changed between observations.

In difference equations the term expressing the size of the stock at time t+1 (the left-hand side of the above equation) is expressed in terms of the size of the stock in time t (the right-hand side of the above equation). If there is a sequence of observational data expressed in this way,

S2 = S1 + gain

S3 = S2 + gain

S4 = S3 + gain

...

and the gain is following some sort of regularity, then one can say that the data in this sequence is expressed as a function of other data in the sequence. The sequence hence is generated recursively. It grows, so to speak, out of itself.

Example: The terms of the famous Fibonacci-sequence

1 1 2 3 5 8 13 21 34 55 89 …

are generated by summing the two preceding terms of the sequence, starting from the two initial terms 0 and 1. Formally this can be written

Fn = Fn-1 + Fn-2 with F0 = 0 and F1 = 1

Some interactive recursion examples:

Pythagoras-tree Koch-snowflake Mandelbrot-set
Iterate up Iterate down

For iterating the Mandelbrot-set, simply click into the picture.

Yet another example are Lindenmayer-systems:

lindenmayer

Modeling branches of plants through iterated division and addition of lines in certain angles. Left: initial geometrical figure, right after five iterations (step 4 is not shown).