Recursion
|
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 Fibonacci Numbers:
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:
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:
Student: So in each of these, we have the starting stage and the rule for moving to the next stage. Mentor: Yes! |
