Recursion 1

From Huben's Wiki
Jump to: navigation, search

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

  1. Stop the recursion (AKA "bail out"): know when the problem is simple enough to solve directly, and return that result.
  2. Divide the problem into smaller parts.
  3. Recurse (call the method) on the smaller parts.
  4. 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.
  1. Draw an arrow to the test that determines whether recursion stops or continues.
  2. Write how the problem is divided into smaller parts.
  3. Underline the recursive call.
  4. Draw arrows to where the results are combined and returned.
Personal tools