Recursion is one of the major tools of computing. (Iteration is another, and the next.)
Recursion means a method calls itself as part of solving a problem. If all a method did was call itself forever, that would be infinite recursion, which is a waste: almost always, there is some way for recursion to stop.
You have already seen recursion in sequences in algebra, most notably the Fibonacci sequence. a0 = 1, a1 = 1, an = an-1 + an-2.
Fractals are geometric examples of recursion:
- Do Handout 1: Sierpinski's Triangle
Count M&M's 2 ways exercise.
Recursive methods generally have 4 parts (though some are often vestigial or combined):
- Stop the recursion (AKA "bail out"): know when the problem is simple enough to solve directly, and return that result.
- Divide the problem into smaller parts.
- Recurse (call the method) on the smaller parts.
- Combine and return the results of the recursion on the smaller parts.
- How do these parts apply to the Sierpinski's Triangle exercise?
- How do these parts apply to the count M&M's exercise?
Handout 2: Describing Recursive methods
- Do the first 3.
- Mark these 4 things on the handout.
- Draw an arrow to the test that determines whether recursion stops or continues.
- Write how the problem is divided into smaller parts.
- Underline the recursive call.
- Draw arrows to where the results are combined and returned.