Overview

• A bit of info about the quiz (topics, general forms of questions)
• Your questions on recent topics
• Sample quiz questions

About the Quiz

What's on the quiz?

Recursion (over lists)

More Recursion (using helpers)

And More Recursion (over numbers)

Husk/Kernel

Named Let and Letrec

Characters and strings

What kinds of questions might you ask?

"Read this recursive procedure and tell me what's wrong with it."

"Given this partially completed procedure, fill in the blanks."

"Show the steps when I apply this procedure to *this input."

"Here's documentation for this procedure. We've written a partial test suite. Please add two more useful tests that stress the procedure in different ways."

"Read this procedure, tell me what it does, give me the preconditions, and rewrite it so that it's clearer. (Probably only two of the three.)

General Questions

Can you talk to us about base cases? How do you decide what they are and when to have them?

Reminders: Really general forms for recursive procedures

    (define PROC
      (lambda (PARAMS)
        (if (SIMPLE? PARAMS)
            BASE-CASE
            (COMBINE (PART-OF PARAMS) (PROC (SIMPLIFY PARAMS))))))

    (define PROC
      (lambda (PARAMS)
        (HELPER (MOST-OF PARAMS) (PART-OF PARAMS))))
    (define HELPER
      (lambda (REMAINING SO-FAR)
        (if (SIMPLE? REMAINING)
            (SOMETHING SO-FAR)
            (HELPER (SIMPLIFY REMAINING) 
                    (COMBINE (PART-OF REMAINING) SO-FAR)))))

Issue one: When are things simple enough that we can stop? A few common cases:

Empty list (null? PARAMS) - is there a natural answer that you can give for the empty list.

One-element list (null? (cdr PARAMS)) - Do we need at least one value?

0 or 1 (when doing numeric recursion)

Many more. If we're looking for a value in a list (e.g., an even number in a list of numbers), the base case can be "that value is the first number in the list". If we're counting from M to N, the base case is probably "our counter has reached N"

Once you've identified that you've reached the base case, how do you decide what to return? First question I ask myself: What type of value are we computing. If I'm trying to build a list, I need to return a list. If I'm trying to build a number, I need to return a number. If I'm trying to compute a color, I need to return that color.

If we're doing helper recursion, the base case almost always involves returning the SO-FAR value. One strategy: Just return that value and see what happens. If it looks good, you're done. If it doesn't look right, think about the relationship of what you get to what you want.

Can we do a long and complicated example?

Sure. Let's find the average of a list of irgb colors.

    (define irgb-average
      (lambda (colors)

Direct recursion vs. helper recursion vs. ???

Suppose I have the list '((irgb 255 0 0) (irgb 100 100 100) (irgb 0 25 74)) Does computing the average of '((irgb 100 100 100) (irgb 0 25 74)) help me find the average of the whole list?

Let's simplify the example. We just want to compute the average of a list of numbers. Suppose I have the list '(1 100 24 5). Does computing the average of (100 24 5) help me?

The first average is (/ (+ 1 100 24 5) 4). The second average is (/ (+ 100 24 5) 3). Dividing by three does not really help us compute something that requires dividing by four.

So we either want to divide each by the length and then add them up, or add them up and divide by the length.

    (define average
      (lambda (nums)
        (average-helper nums 0 0)))

    (define average-helper
      (lambda (remaining sum-so-far length-so-far)
        (if (null? (cdr remaining))
            (/ (+ (car remaining) sum-so-far) (+ 1 length-so-far))
            (average-helper (cdr remaining)
                            (+ (car remaining) sum-so-far)
                            (+ 1 length-so-far)))))

Update one: Check for the empty list in advance

    (define average
      (lambda (nums)
        (when (null? nums)
          (error "average: requires a non-empty list of numbers"))
        (average-helper nums 0 0)))

Update two: Make null the default case

    (define average-helper
      (lambda (remaining sum-so-far length-so-far)
        (if (null? remaining)
            (/ sum-so-far length-so-far)
            (average-helper (cdr remaining)
                            (+ (car remaining) sum-so-far)
                            (+ 1 length-so-far)))))

Can you talk a bit more about husk and kernel?

Some procedures will fail miserably if you give them "bad" inputs. (Don't meet the preconditions). Instead of having weird errors appear, why not give a clear error message.

The husk does the error checking.

The kernel does the real work, assuming that the inputs are good.

Sample Quiz Questions

Can you give a sample quiz question that involves strings?

Let's remove all of the vowels from a string. E.g., "Rebelsky" > "Rblsky"

Zeroeth step; Bring up the documentation on strings so that we can remember what procedures are available.

First step

    (define remove-vowels
      (lambda (str)
        (if (null? str)
            str     ; or ""
            (___ (?? str) (remove-vowels (??? str))))))

Recursion model: Suppose we successfully remove the vowels from "ebelsky", giving us "blsky". How do we get the "Rblsky".

    (define remove-vowels
      (lambda (str)
        (if (null? str)
            str     ; or ""
            (string-append (substring str 0 1) 
                           (remove-vowels (substring str 1))))))

Whoops! Forgot to check if the first character is a vowel!

Whoops! Check for the empty string with (equal? "" str), not with (null? str).

    (define remove-vowels
      (lambda (str)
        (if (equal? "" str)
            str     ; or ""
            (if (member (string-ref str 0) '(#\a #\e #\i #\o #\u))
                (remove-vowels (substring str 1))
                (string-append (substring str 0 1) 
                               (remove-vowels (substring str 1)))))))