# 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:

S_{t}_{+1}
= S_{t} + *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,

S_{2} = S_{1} + gain

S_{3} = S_{2} + gain

S_{4} = S_{3} + 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

F_{n}
= F_{n-}_{1} + F_{n-}_{2}
with F_{0} = 0 and F_{1} = 1

## Some interactive recursion examples:

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

### Yet another example are Lindenmayer-systems:

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).