Held: Friday, 18 March 2016

Back to Outline 31 - Pause for Breath. On to Outline 33 - Naming Local Procedures.

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 32 (Source 32)

Overview

• Recursion, generalized.
• Numeric recursion.

Administrivia

• Continue partners!
• I'm back!
• Have a great break. Be well and be safe.

Reminders

• Office hours this week
  • See http://rebelsky.youcanbook.me.
  • Ask me about other available times.
• Tutor hours
  • Sunday, 3-5 p.m.
  • Sunday-Thursday, 7-10 p.m.
• Weekly review sessions:
  • Wednesday at 8pm in the CS Commons with
  • Thursday 10 am review session with Sam.
  • Thursday at 8pm in the CS Commons with

Upcoming Work:

• Reading for Monday after break
  • Local Procedure Bindings
• Lab Writeup:
  • Send email titled CSC 151 Lab Writeup 32 (Your Names)
  • Do not include the underscores.
  • Send to CSC151-02-grader@grinnell.edu
  • Due before class on Monday after break.

Extra Credit

• Send your reports to rebelsky@grinnell.edu with subject "CSC 151 Extra Credit". (Do not include the quotation marks.)
• Send opportunities to me before class with subject "CSC 151 EXTRA CREDIT OPPORTUNITY!"

Academic / Artistic

• Cinderella on April 6 (I think).

Peer

Regular Peer

• Social Dance Workshop Tuesdays 7:00-8:00 in Bucksbaum Dance Studio
• Pun club Saturdays at 4pm in Younker
• Electronic Potpourri on KDIC Fridays at Five
• Space Odyssey KDIC Fridays at Six
• Bollywood, Friday, 7:30-8:30, Younker
• Effective Altruism club, 2:30-3:30 Sundays in JRC 226.

Misc

Far in the Future

• Lords of the Flies, April.
• Post-break ExCo on British Politics Wednesdays at 8:00 in JRC 203.

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