Held: Friday, 7 March 2014

Back to Outline 27 - Other Forms of List Recursion. On to Outline 29 - Pause for Breath.

Summary

We visit a slightly different kind of recursion, numeric recursion. In this technique, we once again have procedures call themselves. However, the parameter that we "simplify" at every step is a number, rather than a list.

Related Pages

• Reading: Numeric Recursion
• Lab: Numeric Recursion
• EBoard 28 (Source 28) (HTML 28) (PDF 28)

Overview

• Recursion, generalized.
• Numeric recursion.

Administrivia

• No reading for Monday.
• Today's lab writeup: Exercise 4
  • CSC 151.02 Writeup 19: Numeric Recursion
• Mr. Stone will be teaching today.
• No quiz today!
• Continue with your partners from Tuesday.
• Extra credit for any volunteer to do an eboard for today.
• Extra credit:
  • Balancing Acts
    • Friday, 7 March at 7:30 in Flanagan
    • Saturday, 8 March at 7:30 in Flanagan
    • Sunday, 9 March at 2:00 in Flanagan
  • Neverland Players this weekend
    • Friday, 7 March at 7:00 in the Wall
    • Saturday, 8 March at 2:00 in the Wall
    • Saturday, 8 March at 7:00 in the Wall
    • Sunday, 9 March at 2:00 in the Wall
  • Men's Tennis, Saturday, 8 March (8 am or 4pm)

Patterns of Recursion

While we've seen and written a variety of examples of direct recursion, they typically have the following form:

(define *recursive-proc*
  (lambda (*params*)
    (if (*base-case-test*)
        (*base-case* *params*)
        (*combine* (*partof* *params*)
                   (*recursive-proc* (*simplify* *params*))))))

For lists, the simplification was almost always "take the cdr" and the "part-of" was almost always "take the car".

Recursion with Numbers

• While most of the recursion we've been doing has used lists as the structure to recurse over, you can recurse with many different kinds of values.
• It is fairly common to recurse using numbers.
• The natural base cases for integers are when you hit 0 or when you hit 1.
• The natural simplification step for recursive procedure using numbers calls typically involves subtracting 1 from the argument.
  • Other simplifications, such as dividing in half, are also possible.

Lab

• Do the lab