Overview

• You ask questions, I attempt to answer.
• We talk about the forthcoming quiz.

Admin

• Can we ask individual questions if there are only a few of us here? Yes.

Your Questions

What kinds of recursion will be on the quiz?

Direct recursion. (The stuff we did last week.)

Recursion with helper procedures. (The stuff we did on Monday and Tuesday.)

Recursive predicates. (E.g., irgb-secretary-of-state?, which we wrote yesterday.)

Patterns of recursion.

How does display work? Why do we use it?

display prints out a message (more or less, any Scheme expression).

It was designed so that programmers can write interactive programs.

We use it to track what our programs are doing.

Let's look at an example

    (define my-length
      (lambda (lst)
        ; Let's watch every time it's called
        (display (list 'my-length lst))
        (newline)
        ; Here's the normal computation
        (if (null? lst)
            0
            (+ 1 (my-length (cdr lst))))))

    > (my-length (list 1 2 3))
            (my-length '(1 2 3))
            (my-length '(2 3))
            (my-length '(3))
            (my-length '())
    3

So I can track what it does, and whether that matches what I expect it to do?

What Will the Quiz Look Like?

It will likely have some code reading and some code writing.

Sample code-reading questions

What is wrong with this procedure to do X? Fix it.

    (define smallest
      (lambda (lst)
        (if (null? lst)
            0
            (if (> (car lst) (smallest (cdr lst)))
                (car lst)
                (smallest (cdr lst))))))

We've said that if you have an empty list, the smallest value is 0. That feels okay. It's our normal process of "return some junk when the input doesn't make sense". The danger! If we use that 0, and we have only positive numbers, 0 is smaller than those numbers, and so there's a chance that we always return 0.

Better: Use a singleton list as the base case.

        (if (null? (cdr lst))
            (car lst)
            0

If the car is larger than the smallest remaining element, we return the car. That doesn't seem to be the smallest value. E.g., (smallest (list 5 1 2 -4)). 5 is greater than -4, so we return 5. Whoops.

            (if (< (car lst) (smallest (cdr lst)))

Nested ifs are ugly. That's more style than correctness, but ...

    (define smallest
      (lambda (lst)
        (cond
          [(null? (cdr lst))
           (car lst)]
          [(< (car lst) (smallest (cdr lst)))
           (car lst)]
          [else
           (smallest (cdr lst))])))

Don't call (smallest (cdr lst)) twice! That leads to exponential growth in the running time.

    (define smallest
      (lambda (lst)
        (if (null? (cdr lst)
            (car lst)
            (let ([smallest-remaining (smallest (cdr lst))])
              (if (< (car lst) smallest-remaining)
                  (car lst)
                  smallest-remaining))))))

What does this procedure do?

    (define whatever
      (lambda (lst)
        (kernel lst null)))

    (define kernel
      (lambda (remaining so-far)
        (if (null? remaining)
            so-far
            (kernel (cdr remaining) (cons (car remaining) so-far)))))

How would you start thinking about this?

• Look at the name. Sam chose a bad name.
• Look at the general form. This uses helper recursion. So focus on the kernel procedure.

• Try a sample input. Whatever takes a list as a parameter. We'll use the list '(1 2 3 4).

  (whatever '(1 2 3 4))
  (kernel '(1 2 3 4) null)
  (kernel '(2 3 4) (cons 1 null))
  (kernel '(2 3 4) '(1))
  (kernel '(3 4) '(2 1))
  (kernel '(4) '(3 2 1))
  (kernel '() '(4 3 2 1))
  '(4 3 2 1)
  

• It appears that this reverses the list.

What messages will we see when we evaluate the expression below?

    (define my-length
      (lambda (lst)
        (display (list 'my-length lst))
        (newline)
        (if (null? lst)
            0
            (+ 1 (my-length (cdr lst))))))

    (define largest
      (lambda (lst)
        (if (= (my-length lst) 1)
            (car lst)
            (max (car lst) (largest (cdr lst))))))

    > (largest (list 5 1 -3 8))
            (my-length '(5 1 -3 8))
            (my-length '(1 -3 8))
            (my-length '(-3 8))
            (my-length '(8))
            (my-length '())
            ; Computes 4
    (max 5 (largest '(1 -3 8)))     ; Not shown, but included for our use
            (my-length '(1 -3 8))
            (my-length '(-3 8))
            (my-length '(8))
            (my-length '())
            ; Computes 3
    (max 5 (max 1 (largest (-3 8))))

This is why I tell you to use (null? (cdr lst)) instead of (= (length lst) 1). The latter is really inefficient.

What will the output of the following expressions be?

Sample code-writing questions

Fill in the missing parts in this recursive procedure.

    (define smallest
      (lambda (lst)
        (if ___________
            (car lst)
            (______ (car lst) (smallest (cdr lst))))))

A solution

    (define smallest
      (lambda (lst)
        (if (null? (cdr lst))
            (car lst)
            (min (car lst) (smallest (cdr lst))))))

Write a recursive procedure to do the following.

Write a recursive procedure to find the last element of a list. You may not use list-ref or reverse.

    (define last
      (lambda (lst)
        (if (null? (cdr lst))
            (car lst)
            (last (cdr lst)))))

Write a recursive procedure to determine if all of the elements of a list are divisible by three.

Thought process: If the car is divisible by three, move on. Otherwise, return false.

    (define all-divisible-by-three?
      (lambda (lst)
        (if (not (divisible-by-three? (car lst)))
            #f
            (all-divisible-by-three? (cdr lst)))))

    (define divisible-by-three?
      (lambda (val)
        (integer? (/ val 3))))

    (define divisible-by-three?
      (o integer? (r-s / 3)))

    (define divisible-by-three?
      (lambda (val)
        (zero? (remainder val 3))))

We don't really need the procedure. We can write

    (define all-divisible-by-three?
      (lambda (lst)
        (if (not (integer? (/ (car lst) 3)))
            #f
            (all-divisible-by-three? (cdr lst)))))

Are we done? No! There's no base case. If the list is empty, we try to take the car and get an error message.

    (define all-divisible-by-three?
      (lambda (lst)
        (cond
          [(null? lst) #t]
          [(not (integer? (/ (car lst) 3)))
            #f]
          [else
           (all-divisible-by-three? (cdr lst))])))

But we don't like you writing recursive predicates this way. You have a pattern.

    (define all-divisible-by-three?
      (lambda (lst)
        (or (null? lst)
            (and (integer? (/ car lst) 3)
                 (all-divisible-by-three? (cdr lst))))))

This corresponds to how we think about it in English. (I would prefer something like this on the quiz, but won't require it.)