# Recursion 1

From Huben's Wiki

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. a_{0} = 1, a_{1} = 1, a_{n} = a_{n-1} + a_{n-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.