CSC 151.01, Class 22: Numeric recursion

Overview

• Preliminaries
  • Notes and news
  • Upcoming work
  • Extra credit
  • Questions
• Quiz discussion
• Debrief from prior class
• Lab
• Debrief

Preliminaries

News / Etc.

• New partners!
• I hope that you are starting to recover from the time switch.
• We will have one mentor session this week at 7pm on Thursday. The intent is more of an opportunity to talk broadly about CS than about the quiz. (A panel of mentors.)

Upcoming work

• Lab writeup for class 22: Exercise 5. Due before class Wednesday.
• Reading for Wednesday
  • Naming local procedures
• Assignment 6 due Tuesday.
• Flash Cards due Wednesday.
• Quiz Friday: Identify your classmates.
  • You will get pictures and names
  • You will get both given names and class names

Extra credit (Academic/Artistic)

• Visit the two exhibits at the Faulconer Gallery.
• CS Extra TODAY at 4:15 p.m. in 1023: “An Introduction to the Automatic Extraction of Keyphrases”. (Snacks at 4pm.)
• CS Table Tuesday at noon: Unknown topic.

Extra credit (Peer)

Extra credit (Recurring peer)

• Listen to KDIC Wednesdays at 6pm - Witty banter with other personalities and/or co-host. Also Indian, Arabic, and Farsi music.
  (Up to two units of extra credit.)
• Peer editing with SS. Talk to SS about the details. Make your English Lit more literate.

Extra credit (Misc)

• Host one or more prospective students.

Other good things

Questions

We already know how to use filter, map, and reduce. Why are you making us write recursive patterns for them?

Our goal is to empower you to write new things. The map and reduce patterns are simpler than other patterns of recursion and the operation is familiar. We’d rather start with something (comparatively) simple.

Won’t you feel empowered being able to write them yourself?

Quiz discussion

Problem 1

(define select-word
  (lambda (str i)
    (list-ref (string-split str " ") i)))

Quick discussion with partner: What are the reasonable preconditions?

• str must be a string
• i must be an exact integer
• i must be at least zero
• i must be less than the number of words in str

Note: You should test that i is an integer before you test that it is exact or non-negative.

Problem 2

> (first-elements (list (list ’a ’b) (iota 10) (make-list 4 "let’s"))
’(a 0 "let’s")
> (first-elements (list (list ’a ’b ’c) (list ’d) (list "eeee") (list 4 5)))
’(a d "eeee" 4)

We can solve this with (map car lst). But the issue here is what the common recursive map pattern looks like. That is, I’m converting one list to another by applying a procedure to each element of the first list.

With your partner, develop that pattern/template.

(define MAP-PROC
  (lambda (lst)
    (if (null? lst)
        null
        (cons (PROC (car lst))
              (MAP-PROC (cdr lst))))))

If we’ve developed that pattern, and we just want the car of each element.

(define first-elements
  (lambda (lst)
    (if (null? lst)
        null
        (cons (car (car lst))
              (first-elements (cdr lst))))))

Debrief from prior class

What I hoped that you would do for any-odd?

Here’s my template.

(define any-PRED?
  (lambda (lst)
    (and (not (null? lst))
         (or (PRED? (car lst))
             (any-PRED? (cdr lst))))))

Oh, I guess I need a predicate for “It’s an odd integer”. I can write that.

(define odd-integer?
  (lambda (val)
    (and (integer? val) (odd? val))))

Now I’m in my normal state of copy, paste, change

(define any-odd?
  (lambda (lst)
    (and (not (null? lst))
         (or (odd-integer? (car lst))
             (any-odd? (cdr lst))))))

Refining the solution

We can rewrite odd-integer? with conjoin.

(define odd-integer?
  (conjoin integer? odd?))

Scheme just replaces procedures with their bodies; we can do the same.

(define any-odd?
  (lambda (lst)
    (and (not (null? lst))
         (or ((conjoin integer? odd?) (car lst))
             (any-odd? (cdr lst))))))

Lab

I don’t understand how the “divide by two” example reaches zero.

(define RECURSIVE-PROC
  (lambda (n)
    (if (zero? n)
        BASE-CASE
        (COMBINE n (RECURSIVE-PROC (quotient n 2))))))

quotient rounds down. If you keep dividing by two, you’ll eventually add up at 1. (quotient 1 2) is 0.

Could you explain that section comment in problem 5?

Once you’ve defined powers-of, you can implement powers-of-two as a call to powers-of (or at least in terms of powers-of). That way, we don’t need duplicated code.

Often, when we define one procedure in terms of another, we use section.

Debrief

Writing iota

The typical solution for iota requires a combination of helper recursion and direct recursion. That is, we’re going to use a helper, but the helper is going to do direct recursion.

One issue: We want to count up to n. That suggests an extra parameter. for our counter. (That’s the thing we normally call i.)

The other issue: We want the individual values to go at the front. If we use so-far, they go at the end.

(define iota 
  (lambda (n)
    (iota-helper 0 n)))

; Compute the list '(i i+1 i+2 ... n-1)
(define iota-helper
  (lambda (i n)
    (if (= i n)
        null
        (cons i (iota-helper (+ i 1) n)))))

    ...))

Lists of powers

What I would have liked for powers-of-two … coming next class.