Outline 29: Numeric Recursion

Held: Friday, 17 October 2014

Back to Outline 28 - Other Forms of List Recursion. On to Outline 30 - Preconditions, Revisited.

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

Overview

Recursion, generalized.
Numeric recursion.

Administrivia

Retain partners
No office hours next week!
Some discussion of patterns in yesterday's eboard.

Upcoming Work

Reading for the Monday after break
- Verifying Preconditions

Extra Credit Opportunities

Academic

CS Table, Today: Hear about the Grace Hopper Celebration of Women in Computing.

Peer Support

Football (Saturday at 1pm)
Swimming October 18: Alumni Weekend
Karan's radio show 11pm Thursday nights on KDIC
Evan's radio show 5pm Friday nights on KDIC
Donna's radio show Sunday midnight on KDIC
Men's Tennis (???)
Women's Tennis (???)

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 (PART-OF 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