Student: Tell me about
recursion. Is it the same as iteration or not?
Mentor: Recursion is a special kind of
iteration. Here's the idea: With a recursion we are given starting information and a rule for how to
use it to get new information. Then we repeat the rule using the new information as though it
were the starting information.
Student: So we have a loop? What comes out of the rule goes back into the rule for the next iteration?
Mentor: That's a good way to think about it. Here's a classic example of a recursion which cranks out
a sequence of numbers called the
Here we have starting information and a rule for generating a new value. The n increases by
one each time, so we can ask questions like
find the ninth fibonacci number. We are given two starting values since each new value is calculated from the two previous
ones. Try generating the ninth number.
Student: Let's see. The first numbers are 1 and 1, as given. The rule says to take the two previous
numbers and add them to get the new number, so I would get:
n = 3:
1 + 1
n = 4:
1 + 2
n = 5:
2 + 3
n = 6:
3 + 5
n = 7:
5 + 8
n = 8:
8 + 13
n = 9:
13 + 21
Mentor: Good! Now let's consider the
fractal examples we have seen so far. For fractals, the starting information is called the initiator,
the rule for iterating is called the generator: