CSC151.02 2016S, Class 25: Recursion Basics
===========================================

_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](../readings/recursion-basics-reading.html)
* 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
------------------------------