EBoard 19: Numeric recursion

Approximate overview

• Admin
• Notes from last class
• Lab

Administrative stuff

Introductory notes

• Please disinfect your keyboard and mouse; there are many colds and such going around campus.
• Reminder: If Gradescope says that it can’t read your Racket file, please use File -> Save Other -> Save Definitions As Text…
  • Do you know what the ellipses in a menu item signify?
  • Don’t worry about the text files.
• Sorry about the incorrect timing on Convocation.
• I hope to show off your cool analyses on Monday.

Friday PSA

A new variant?

• Reminder: By fall break, half of first-years report never having consumed alcohol. In general 30% of Grinnellians say they have not drunk in the past two weeks.
• I have no idea what the number is for drugs, but I’m pretty sure that only 20% or so report having used drugs in the past two weeks.
• 30% of Grinnellians report no sexual partners in the past year; 30% report only one; 40% other.
  • Consent is ESSENTIAL

Another new variant?

• 1010
• Please behave reasonably.

Upcoming activities

Events

• WGMC Friday at 4pm.
• Today at 4:30, Time Trials
• Mentor Session Sunday at 4pm.
• Arcadia this weekend!
  • Arcadia is a play by Tom Stoppard
  • Tickets are “on sale” at noon today.
• MET Opera Saturday at 11:55 a.m. in Harris Cinema. Boris Godunov.
• Football Saturday at 1:00 p.m.
• Celebrate 10/10 appropriately.
• 7pm Monday the 11th: Jillian Peterson on The Violence Project.
• CS Extras Thursday at 4pm: ???

Other good things

Upcoming work

• SoLA 2 next week! A chance to show off all that you’ve learned.
• No readings for Monday. Monday is simply more chance to practice with recursion.
  • Yay, fun!
• Lab Writeup due Monday morning.

Q&A

Notes on Recursion

Thinking about recursion

• Many of you are trying to think of recursion as a loop. Don’t; it tends to get in the way.
• Assume that you’ve solved the problem already and can call the procedure on a “smaller” input.
• How does that help you solve the problem on slightly larger input?
• Then figure out when the input is “small enough” that you can solve the problem directly.
  • The test for “small enough” is your base-case test.
  • The value you return in that case is your base case.
• The magic recursion fairy (or what we’ve learned watching traces) makes it all work.

Four ways of writing longest-string

Using the big three.

(define longer-string
  (lambda (str1 str2)
    (if (>= (string-length str1) (string-length str2))
        str1
        str2)))

(define longest-string
  (lambda (strings)
    (reduce longer-string strings)))

Using recursion and that helper procedure we just wrote.

• Base case test: A list of one element
• (car lst) gives the first element of the list
• (cdr lst) gives all but the first element of the list.

;;; (longest-string strings) -> string?
;;;   strings : list-of string? nonempty?
;;; Finds the longest string in a list of strings.
(define longest-string
  (lambda (strings)
    (if (one-element? strings)
        (car strings)
        (longer-string (car strings) (longest-string (cdr strings))))))

Using recursion without that helper procedure we just wrote.

(define longest-string
  (lambda (strings)
    (if (one-element? strings)
        (car strings)
        (if (>= (string-length (car strings)) 
               (string-length (longest-string (cdr strings))))
            (car strings)
            (longest-string (cdr strings))))))

Or as

(define longest-string
  (lambda (strings)
    (cond
      [(one-element? strings)
       (car strings)]
      [(>= (string-length (car strings))
           (string-=length (longest-string (cdr strings))))
       (car strings)]
      [else
       (longest-string (cdr strings))])))

Hmmm … This takes a really long time on the list ‘(“a” “aa” “aaa” … “aaaaaaaaaaaaaaaaaaaaaaaaaaaaa”). Why?

Using recursion and local bindings.

(define longest-string
  (lambda (strings)
    (if (one-element? strings)
        (car strings)
        (let ([str1 (car strings)]
              [str2 (longest-string (cdr strings))])
          (if (>= (string-length str1)
                  (string-length str2))
              str1
              str2)))))

Morals

• Don’t forget the old stuff, but accept that Sam is generously cruel and makes you rewrite things using recursion.
• Pattern of recursion: Think about what you can do if you solve a “smaller” input (using the procedure that future you writes).
• Helpers are helpful. longer-string
• Sometimes subtle issues in our code make things run slowly.
• Lets are helpful.

The actual code

#lang racket
(require rackunit)
(require csc151)

(define longer-string
  (lambda (str1 str2)
    (if (>= (string-length str1) (string-length str2))
        str1
        str2)))

;;; (one-element? lst) -> boolean?
;;;   lst : a list
;;; Determines if lst has one element.
(define one-element-that-will-get-sam-to-yell-at-you!?
  (lambda (lst)
    (= (length lst) 1)))
(define one-element?
  (lambda (lst)
    (and (not (null? lst))
         (null? (cdr lst)))))

;;; (longest-string strings) -> string?
;;;   strings : list-of string? nonempty?
;;; Finds the longest string in a list of strings.
(define longest-string1
  (lambda (strings)
    (if (one-element? strings)
        (car strings)
        (longer-string (car strings) (longest-string1 (cdr strings))))))

(define longest-string2
  (lambda (strings)
    (cond
      [(one-element? strings)
       (car strings)]
      [(>= (string-length (car strings))
           (string-length (longest-string2 (cdr strings))))
       (car strings)]
      [else
       (longest-string2 (cdr strings))])))

(define longest-string3
  (lambda (strings)
    (if (one-element? strings)
        (car strings)
        (let ([str1 (car strings)]
              [str2 (longest-string3 (cdr strings))])
          (if (>= (string-length str1)
                  (string-length str2))
              str1
              str2)))))

(define longest-string longest-string3)

(test-equal? "test 1" (longest-string '("hello" "hi")) "hello")
(test-equal? "test 2" (longest-string '("one")) "one")
(test-equal? "test 3" (longest-string '("a" "list" "of" "like" "twenty" "strings" "or" "just" "longer" "than" "two")) "strings")
(test-equal? "test 4" (longest-string '("a" "list" "of" "like" "twenty" "strings" "or" "just" "longer" "than" "two" "longest-string")) "longest-string")
(test-equal? "test 5" (longest-string '("longest-string" "a" "list" "of" "like" "twenty" "strings" "or" "just" "longer" "than" "two")) "longest-string")

(define long-list (map (section make-string <> #\a)
                       (range 1 30)))

Lab

We will continue partners and computers and lab on Monday.

Prep

• Person nearest the board is A.
• Person furthest from the board is B.
• If you are confused about distance, ask a mentor.
• Please read through the initial procedures! (Whoops, there are no initial procedures.)

Notes during lab

Think of the second set of calls to acc-range as a trace.

    (acc-range 4 '())
--> (acc-range 3 '(4))
--> (acc-range 2 '(3 4))
--> (acc-range 1 '(2 3 4))
--> (acc-range 0 '(1 2 3 4))
'(1 2 3 4)

What happens to the first parameter to acc-range at each step?

What happens to the second parameter to acc-range at each step?