• Continue partners!
• Enjoy food-like substances!

Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• Some challenges.
• The idea of recursion.
• Challenges, re-expressed in Scheme.
• Expressing recursion in Scheme.
• Lab.

Preliminaries

Admin

• Office hours
  • Normal (MThF 1:45-3:15; walking 1:15-1:45)
  • In the Grill 8:00-9:30 am Fri
  • In my office 8:00-9:30 am Tue and Thu
• Evening review sessions tonight at 8pm and Thursday at 8pm
• Daytime review session Thursday at 10:00 a.m.
• Quiz 5 will be returned Friday. (We had a mixup with one student who still needs to take it.)

Upcoming Work

• No writeup today! (There will be a writeup on this lab, but it will be assigned Friday.)
• Exam 2
• Reading for Friday:
  • Reread Recursion Basics
• Quiz Friday

Topics for Friday's Quiz

My quiz policies will continue through this week. You may bring a page of notes. You will not have a time limit, although I will encourage you to try to finish in ten minutes.

• Lists, particularly cons, car, cdr, and null?
  • We might ask you to write instructions to build a list.
  • We might give you some instructions and ask yo to interpret them.
  • We might challenge you to think about lists and non-lists (issues raised by the now-renamed one-two, won-too, and want-to)
• image-compute!
  • We might ask you to interpret some code. ("Sketch the image that this code creates ...")
  • We might ask you to write instructions to create a particular image (given verbally or pictorially).
  • We might do a hybrid ("Fill in the blanks to achieve ...")
• Local bindings with let and let*
  • The relationship(s) between the two
  • Ordering of let and lambda
• Any previous topics are also fair game, although they will probably be incorporated in the previous kinds of problems.
  • We might ask for an anonymous procedure
  • We might have problems that require conditionals
  • We might combine the earlier list procedures with the newer ones
  • ...

Cool Things Coming to Campus

• Two versions of Anna Christie!
• Live Streaming of Verdi's Macbeth, Saturday at 11:55 a.m.
• Pop-up Exhibit, Thursday October 9th, all day in BCA 132

Extra Credit Opportunities

Academic

• Grinnell Prize events this week (particularly events related to the prize winners whose project involves Web tools)
• Artist Talk, Wednesday October 8th at 4:15pm in BCA 152 Rewriting the Application Programming Interface (API) for Art Making
• BCC Faculty Chat, Tuesday, October 14, 7pm

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
• The College's version of Anna Christie, Oct. 9-12 (SB plays Marthy)
• Men's Tennis (???)
• Women's Tennis (???)

Miscellaneous

• Fill in the Grinnell College Web Survey at http://bit.ly/1ncPO5V

Questions

Some challenges

Context:

• We know that the algorithms you write depend on some basic operations.
• Basic operations you are allowed:
  • Anything you've learned earlier in the semester (plus a few other obvious ones)
  • Determine whether or not a list is empty
  • If a list is nonempty, you can hand the remainder of the list to someone else, and ask them a question (almost any question)
• Count a stack of cards
  • Ask your neighbor to count all but the first
  • Add 1 to their result
• Count even numbers in a list of numbers
  • Ask your neighbor to count the number of even numbers in the cdr
  • If your card is even, add 1
  • Otherwise, add 0
• Make a list of even numbers from a list of numbers
  • Ask your neighbor to make the list of even numbers from the cdr
  • If your card is even, cons the card on the the result you got from your neighbor
  • Otherwise, use the result you got from your neighbor

The idea of recursion

• You can solve a problem on a list by
  • Asking a question about the car of of the list
  • Asking someone else the same question with the cdr of the list
  • Combining the results
• "Someone else" can use the same instructions
• At some point, we reach a problem that we can solve vacuously (e.g., when we have the empty list)

Expressing recursion in Scheme - The problems

    ; Given a list, find out how many values are in the list
    (define my-length
      (lambda (lst)
         (if (null? lst)
             0
             (+ 1 (my-length (cdr lst))))))

How does this work?

    (my-length '(1 2 3 4))
    => (if (null? '(1 2 3 4))
           0
           (+ 1 (my-length (cdr '(1 2 3 4)))))
    => (if #f
           0
           (+ 1 (my-length (cdr '(1 2 3 4)))))
    => (+ 1 (my-length (cdr '(1 2 3 4))))
    => (+ 1 (my-length '(2 3 4)))
    => (+ 1 (if (null? '(2 3 4))
                0
                (+ 1 (my-length (cdr '(2 3 4))))))
    => (+ 1 (if #f
                0
                (+ 1 (my-length (cdr '(2 3 4))))))
    => (+ 1 (+ 1 (my-length (cdr '(2 3 4)))))
    => (+ 1 (+ 1 (my-length '(3 4))))
    => (+ 1 (+ 1 (if (null? '(3 4))
                     0
                     (+ 1 (my-length (cdr '(3 4)))))))
    ...
    => (+ 1 (+ 1 (+ 1 (my-length (cdr '(3 4))))))
    => (+ 1 (+ 1 (+ 1 (my-length '(4)))))
    => (+ 1 (+ 1 (+ 1 (if (null? '(4))
                          0
                          (+ 1 (my-length (cdr '(4))))))))
    ...
    => (+ 1 (+ 1 (+ 1 (+ 1 (my-length (cdr '(4)))))))
    => (+ 1 (+ 1 (+ 1 (+ 1 (my-length null)))))
    => (+ 1 (+ 1 (+ 1 (+ 1 (if (null? null)
                               0
                               (+ 1 (my-length (cdr null))))))
    => (+ 1 (+ 1 (+ 1 (+ 1 (if #t
                               0
                               (+ 1 (my-length (cdr null))))))
    => (+ 1 (+ 1 (+ 1 (+ 1 0))))
    => (+ 1 (+ 1 (+ 1 1)))
    => (+ 1 (+ 1 2))
    => (+ 1 3)
    => 4

    ; Given a list of integers, count even numbers in the list
    (define count-evens
      (lambda (lst)
        (cond
          [(null? lst) 0]
          [(even? (car lst)) (+ 1 (count-evens (cdr-list)))]
          [else (count-evens (cdr-list))])))

    ; Given a list of integers, extract the even values and
    ; give back a list of those values
    (define list-evens
      (lambda (lst)
        (cond
          [(null? lst) null]
          [(even? (car lst)) (cons (car lst) (list-evens (cdr-list)))]
          [else (list-evens (cdr-list))])))

Expressing recursion in Scheme - General Pattern

    (define PROC
      (lambda (lst)
        (if (null? lst)
            SOME-VALUE
            (COMBINE (car lst) (PROC (cdr lst))))))

    (define PROC
      (lambda (lst)
        (cond
          [(null lst?) SOME-VALUE]
          [(TEST (car lst?))
            (COMBINE (car lst) (PROC (cdr lst)))]
          [else
            ...])))

Lab