Overview

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

Admin

Your Questions on the Exam

Why is my solution to problem 2 still so slow?

You are converting a string color to an integer-encoded color way too many times. You can figure that out by using the following in place of one of the calls to color->irgb. (It gives the same result, but tells you what's happening.)

    (define color->irgb2
      (lambda (color)
        (let ([result (color->irgb color)])
          (display "Converting ")
          (display color)
          (display " to ")
          (display result)
          (newline)
          result)))

Your Questions on Recursion

What is the difference between a recursive predicate and some other kind of recursive procedure?

We tend to write recursive predicates using and and or.

Other recursive procedures tend to make choices using if or cond.

Can racket ever immediately return false with one of those and/or recursive predicates?

In the following, if the list is empty, it immediately returns true. If the car is not positive, it immediately returns false without looking at the rest of the list.

    (define all-positive?
      (lambda (lst)
        (or (null? lst)
            (and (positive? (car lst))
                 (all-positive? (cdr lst)))))

We can tell that it stops early with the following

    > (all-positive? (list 1 2 "hello"))
    . . positive?: contract violation
      expected: real?
      given: "hello"
    > (all-positive? (list -1 1 2 "hello"))
    #f

When we use and and or to do multiple things, particularly when a latter thing is recursive, what do we continue and when do we stop?

or continues when the first parameter is false

and continues when the first parameter is true

Your Questions on Other Issues

When running the test cases in a test suite, does it run them one at a time, or all at once?

One at a time, from top to bottom.

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 find the smallest value in

 a list of numbers?  (Sam sees three problems: Two obvious and
 one subtle.)

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

It's a bad idea to do cdr twice.

It can be a bad idea to do a nested if.

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

The sign is backwards. Right now, we're finding the largest value.

              (if (< (car lst) smallest-remaining)

Something wrong is the base case. Should 0 really be the smallest number in a list that contains a negative number?

    (smallest (list -5))
    smallest-remaining = (smallest (cdr lst))
    smallest-remaining = (smallest null)
    smallest-remaining = 0
    (if (< (car lst) smallest-remaining)
        (car lst)
        smallest-remaining)
    (if (< -5 0)
        -5
        0)

That worked okay. But something still seems wrong with the base case. What if we had a positive integer.

    (smallest (list 5))
    smallest-remaining = (smallest (cdr lst))
    smallest-remaining = (smallest null)
    smallest-remaining = 0
    (if (< (car lst) smallest-remaining)
        (car lst)
        smallest-remaining)
    (if (< 5 0)
        5
        0)
    0

How do we fix the base case? Use a singleton list as a base case

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

We've learned a new technique for writing smallest (see below)

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)))))

Read through the code. But that may not be obvious.

Identify the type of input. whatever takes a list as an input.

We see that if the list is null, we get so-far.

Try examples.

    (whatever null)
    (kernel null null)
    null
    ; null -> null
    (whatever (list 1))
    (kernel '(1) null)
    (kernel null (cons 1 null))
    (kernel null '(1))
    '(1)
    ; '(1) -> '(1)
    (whatever (list 3 4))
    (kernel '(3 4) null)
    (kernel '(4) '(3))a
    (kernel null '(4 3))
    ; '(3 4) -> '(4 3)

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

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 2))

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))))))

    (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.

Write a recursive procedure to determine if all of the elements in a list are positive?

    (define all-positive?
      (lambda (lst)
        (if (null? (cdr lst))
            (if (positive? (car lst))
                #t
                #f)
            (if (positive? (car lst))
                (all-positive? (cdr lst))
                #f))))

Note

            (if (positive? (car lst))
                #t
                #f)

Can be written more concisely as

            (positive? (car lst))

We'll ignore that issue and just change the base case.

    (define all-positive?
      (lambda (lst)
        (if (null? lst)
            #t
            (if (positive? (car lst))
                (all-positive? (cdr lst))
                #f))))

Sarah T. does not like nested if's (nor do most of us)

We can write predicates using and and or.

    (define all-positive?
      (lambda (lst)
        (or (null? lst)
            (and (positive? (car lst))
                 (all-positive? (cdr lst))))))