CSC 151.01, Class 20: Recursion with helper procedures

Overview

• Preliminaries
  • Notes and news
  • Upcoming work
  • Extra credit
  • Questions
• Debrief from previous class
• Lab
• Debrief

Preliminaries

News / Etc.

• New partners!
• If you’ve done a homework assignment with your current partner, please re-draw a card.
• I reported mid-semester grades last night.
  • If you needed to invoke “There’s more to life” on the first exam, I marked you as “Marginal”.
  • If you did not turn in exam one, I marked you as “Risk of Failure”.
  • In both those cases, I needed to turn in Academic Progress Reports, too.
  • I expect that with support, all of the “Marginal” students will be fine. (Not least because of the never-yet-invoked “good faith grade guarantee”.)
• I’m not sure what the mentors decided on for the mentor sessions on Thursday. They will send out email.
• There was an issue with the generation of the news page. I think I’ve fixed it.
• Some great answers so far on the “What will help you do better next time”
  • Go to Sam’s office hours
  • Convince Sam to write and distribute answer keys for homework assignments.
  • Make notes to myself after each lab/reading.
• Please make sure that the current eboard is up on your computer. We’ll refer to it during class.

Upcoming work

• Cover sheets due now.
• Exam 2 epilogue due tonight.
• Flash Cards due tonight.
• Lab writeup for class 20: Exercise 2. Due before class Friday.
• Quiz Friday
  • Topics
    • Precondition checking
    • Basics of recursion
  • Typical types of questions
    • Write precondition checks (aka “husk”) for this procedure.
    • Show the steps in evaluating this expression with this recursive procedure.
    • Fill in the details to complete the definition of this recursive procedure.
• Reading for Friday
  • List recursion revisited
• Assignment 6
  • These problems should be smaller (more like lab problems), but there are more of them.
  • Please start lab by identifying three hours that you can meet with your partner. Also discuss anything you should or should not do in advance. E.g., “Spend five minutes on each problem thinking about a general strategy, but don’t write any code.”
  • If you are not at least 80% done after those three hours, please let me know.

Extra credit (Academic/Artistic)

• Visit the two exhibits at the Faulconer Gallery.
• CS Extra Thursday at 4:15 p.m. in 3821: “Mobility in a Networked World”

Extra credit (Peer)

• Play this weekend. Thursday through Sunday. See the campus memo or elsewhere for details.
• Men’s Tennis, Sunday at 9am and 2pm in the Field House.
• Escape room postponed.

Extra credit (Recurring peer)

• Listen to KDIC Wednesdays (Tonight) 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. And don’t just write “I hosted a prospie. They are too pretentious for Grinnell. I hope they go to Carleton”.

Other good things

• GHS presents “The Little Mermaid” Thursday, Friday, Saturday.
• Singers concert, Sunday, 4 p.m., Plymouth United Church of Christ, 4126 Ingersoll Ave., Des Moines.

Questions

Debrief from prior class

Exploring computation in recursive procedures

It helps to think about how Scheme evaluates recursive procedures by repeatedly expanding the expression. (We’ve done that in the readings.) For example

(define product
  (lambda (lst)
    (if (null? lst)
        1
        (* (car lst) (product (cdr lst))))))

#|
(product '(5 3 4)) 
    ; lst is not null
  => (* (car '(5 3 4)) (product (cdr '(5 3 4)))) 
    ; simplify the car and cdr
  => (* 5 (product '(3 4)))) 
    ; lst is not null
  => (* 5 (* (car '(3 4)) (product (cdr '(3 4)))))
    ; cdr is the innermost expression
  => (* 5 (* (car '(3 4)) (product '(4))))
    ; car is also an easy to evaluate expression
  => (* 5 (* 3 (product '(4))))
    ; '(4) is not a null list
  => (* 5 (* 3 (* (car '(4)) (product (cdr '(4))))))
    ; We can take the car of '(4) and the cdr of '(4)
  => (* 5 (* 3 (* 4 (product null))))
    ; The list is null.  Use 1!
  => (* 5 (* 3 (* 4 1)))
    ; 4 times 1 is 4
  => (* 5 (* 3 4))
    ; 3 times 4 is 12
  => (* 5 12)
    ; 5 times twelve is an error
    ; 5 times 12 is 60
  => 60

|#

What conditional to use

You will often find that you start by writing if but end up writing a cond expression.

(define tally-numbers
  (lambda (lst)
    (if (null? lst)
        0
        (if (number? (car lst))
            (+ 1 (tally-numbers (cdr lst)))
            (tally-numbers (cdr lst))))))

vs.

(define tally-numbers
  (lambda (lst)
    (cond
      [(null? lst)
       0]
      [(number? (car lst))
       (+ 1 (tally-numbers (cdr lst)))]
      [else
       (tally-numbers (cdr lst))])))

Checking if a list has one element

• Not (= 1 (length lst)).
  • Why not?
  • length is an expensive operation. We really don’t need to ask how many elements are in a list to see if there’s one.
• But rather (null? (cdr lst)).
  • As long as you know that the list has at least one element
• Or perhaps (and (not (null? lst)) (null? (cdr lst)))

Ways to write largest with direct recursion

(define largest
  (lambda (lst)
    (cond
      [(null? (cdr lst))
       (car lst)]
      [(> (car lst) (largest (cdr lst)))
       (car lst)]
      [else
       (largest (cdr lst))])))

(define largest
  (lambda (lst)
    (if (null? (cdr lst))
        (car lst)
        (max (car lst) (largest (cdr lst))))))

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

(define largest
  (lambda (lst)
    (cond 
      [(null? (cdr lst))
       (car lst)]
      [(> (car lst) (cadr lst))
       (largest (cons (car lst) (cddr lst)))]
      [else
       (largest (cdr lst))])))

• No one loves the first one, even though most of you wrote it.
• Some dislike it because it looks inefficient with repeated work.
  • It’s even more inefficient than you think
• The max on is easy to follow. Perhaps easy for the programmer.
  • But yes, we could just use (reduce max lst).
  • We’re getting to the point that you will soon be able to write reduce.
• The let one is more efficient than the first one, plus it has that confusing let that makes me feel superior to the people who can’t read code with lets.
• The cadr one makes more sense; it feels like you only go through the list once.
  • Everyone but the first one only goes throught the list once.
  • But this one goes through the list in the order a normal human being would.
  • Twenty years of teaching this class suggests that ones that use the last strategy will be mostly likely to have a problem.

Writing recursive procedures

Strategy one: “Look for something I’ve already solved that’s similar.”

General strategy: “Trust the magic recursion fairy”

• Assume that you have a procedure that already solves the problem, but only for slightly smaller input (e.g., the cdr of the list).
• Think about how that helps you solve the slightly bigger case.
  • “If I can find the largest value in the cdr of the list, the largest value in the whole list is …”
• Add a base case.

Lab

Don’t forget: Start by planning with your partner! We will check in with you.

Writeup: Exercise 2

Debrief