Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• Background.
• The idea of recursion.
• Some sample recursive procedures.
• Expressing recursion in Scheme.

Preliminaries

Admin

• New partners!
• I'm back. I hope you missed me. I brought you presents.
• I'm extending the due date of the exam for a week.
  
  • Yes, that means you get one fewer homework assignment. I'm sure you'll deal.
  • Unfortunately, I'll be gone next Monday and Tuesday.

Reminders

• Office hours this week
  • See http://rebelsky.youcanbook.me.
  • I'm working on adding more.
  • I'll soon respond to requests for special times.
• Tutor hours
  • Sunday, 3-5 p.m.
  • Sunday-Thursday, 7-10 p.m.
• Weekly review sessions:
  • Wednesday at 8pm in the CS Commons with Evan
  • Thursday review session this week with Sam.
  • Thursday at 8pm in the CS Commons with Kumar

Upcoming Work:

• Reading for Tuesday
  • Revisit: Recursion Basics
• Exam 2 due NEXT TUESDAY.

Extra Credit

• Send your reports to rebelsky@grinnell.edu with subject "CSC 151 Extra Credit". (Do not include the quotation marks.)
• Send opportunities to me before class with subject "CSC 151 EXTRA CREDIT OPPORTUNITY!"

Academic / Artistic

• Tuesday night at 7:30 public events concert.

Peer

• 4:00 p.m. Tuesday, ISO Travel Faire.
• The Tempest. This weekend. 7:30 Friday and Saturday, 2:00 Sunday. Tickets in Bucksbaum box office.
• Tuesday at 11:45 AppDev talks to you about the next great GrinnellApp in DLab (Forum, the least accessible building on campus)

Regular Peer

• Social Dance Workshop Tuesdays 7:00-8:00 in Bucksbaum Dance Studio
• Pun club Saturdays at 4pm in Younker
• Electronic Potpourri on KDIC Fridays at Five
• Space Odyssey KDIC Fridays at Six

Misc

Far in the Future

• Lords of the Flies, April.

No Extra Credit, But Still Good

• Indoor track nationals.

Questions

Background

The primary components of an algorithm

• Variable - A named value
  • In Scheme: let or define
• Subroutine - Like a procedure; like putting butter on bread
  • A named set of instructions
  • Build them with lambda or section or compose
  • We can name procedures with let and define and let*
• Parameters - Named inputs to the subroutine (or the whole algorithm)
  • The things that come after the lambda.
• Sequencing - Ordering the steps in the algorithm
  • Scheme has some models in which it does steps.
  • The definitions in a let are done before the body.
  • The definitions in a let* are done in order.
  • Compound expressions are evaluated inside out.
  • For things at the same level, it seems to be left-to-right.
  • Procedures built with compose apply the procedures right-to-left (compose square increment), increments and then squares.
  • If you have a series of expressions, it evaluates them in order ("top to bottom")
• Conditionals - Handling different situations / making choices
  • if, and, cond, or,
• Repetition - Doing steps in an algorithm again and again and again
  • UM - Use map
  • image-compute - limited form of repetition - computing pixels
  • image-variant - limited form of repetition - changing pixels
  • iota - Making a list?
• Basic operations and values - Things the computer or algorithm already knows.
  • Eg.,. *, modulo, quotient, irgb, ...
• Output - In the end, the algorithm builds or computes something.

The idea of recursion

• We can achieve (general) repetition through delegation
• Counting books
  • Pass all but one on to delegate
  • Ask your delegate to count
  • Add 1 to your delegate's answer
• The delegate counts books
  • Pass all but one on to delegate
  • Ask your delegate to count
  • Add 1

• Improve the algorithm: If there are no books, use a count of 0

  (define count
    (lambda (lst)
      (if (null? lst)
          0
          (+ 1 (count (cdr lst))))))
  

or

    (define count
      (lambda (lst)
        (if (null? lst)
            0
            (increment (count (cdr lst))))))

Goal: Find alphabetically first book by title

• Pass all but one of the books to your assistant/delegatea
• Ask your assistant to find the alphabetically first book
• Choose the alphabetically first of the two titles

Assistant

• Pass all but one of the books to your assistant/delegate
• Ask you assistant to find the alphabetically first book
• Choose the alphabetically first of the two titles

..

• When you have only one book, you know that it's the lightest

  ;;; Precondition:
  ;;;   lst is nonempty
  (define alphabetically-first
    (lambda (lst)
      ; If there's only one element
      (if (null? (cdr lst))
          ; That element is alphabetically first
          (car lst)
          ; Take the rest of the list
          ; Find the alphabetically first
          ; Take the first of the two
          (let ([guess (alphabetically-first (cdr lst))])
            (if (string<=? guess (car lst))
                guess
                (car lst)))
  

Revised code

(define alphabetically-first
  (lambda (lst)
    ; If there's only one element
    (if (null? (cdr lst))
        ; That element is alphabetically first
        (car lst)
        ; Take the rest of the list
        ; Find the alphabetically first
        ; Take the first of the two
        (let ([mine (car lst)]
              [guess (alphabetically-first (cdr lst))])
          (if (string<=? guess mine)
              guess
              mine)))))

Some sample recursive procedures

Expressing recursion in Scheme