Class 17: Recursion with Lists (1)

Held: Monday, 17 February 2003

Summary: Today we investigate recursion over lists with a number of experiments.

Related Pages:

• EBoard.
• Reading on Recursion.
• First Lab on Recursion.
• New Lab on List Recursion.

Due

• Homework 2.

Assignments

• Lab Writeup 2 (optional).

Notes:

• Yes, I know you'd like the lab writeup graded before starting the next lab writeup. It is near the top of my to do list (after preparing tomorrow's classes and grading 153).
• Now that you've done the reputed hardest assignment in Sam's 151, is it worth assigning? (Yes, I'll ask you again nearer the end of the semester.)
• Do you all understand why I make you close your eyes when I ask you to vote on things or admit you're confused?
• If you'd like to play with your classmates' Mad Libs games, you can find URL's in the notes on homework 2 (that's all you'll find there right now).

Overview:

• Reflections on Recursion.
• Lab: List Recursion, Revisited.

Reflection

• I find it useful to think about the pattern one uses to design certain kinds of procedures.
• Here's the pattern of a typical recursive procedure:

  (define proc
    (lambda (val)
      (if (base-case-test)
          (base-case val)
          (combine (partof val)
                   (proc (update val))))))
  

• When the value you're working with is a list and your base case is the null list, the form is somewhat simpler:

  (define proc
    (lambda (lst)
      (if (null? lst)
          null-case
          (combine (onestep (car val))
                   (proc (cdr val))))))
  

• You may even find that there are some boolean procedures that don't even need an if. For example, here's one implementation of member that works on the principle that val is a member of lst if the list is not empty and val is the first element of lst or val is a member of the remainder of lst.

  (define member?
    (lambda (val lst)
      (and (not (null? lst))
           (or (equal? val (car lst))
               (member? val (cdr lst))))))
  

Labs

• Continue working on the first recursion lab.
• Start the second recursion lab.