CSC151 2007S, Class 11: Recursion

Admin:
* Are there questions on HW6?
* I got the topic of tomorrow's Thursday Extra wrong - 
  * It's on the automation of the Athletic Recuriting Practice.
  * Still EC for attending.
* For Friday, please reread the reading on recursion.

Overview:
* Repetition.
* Recursion.
* Recursion in Scheme.
* Lab.

/Key Attributes of Algorithms/

* Values (and types associated with those values)
* Built-in operations that can be applied to those values
  E.g,. turn
  E.g.  +
* Variables - Named values
  E.g., "The slice of bread in your dominant hand"
* Sequences of operations
  * Parenthesization
  * Each statement gives output, so you do one after another
* Our own Subroutines - Procedures
  * What the procedure is and does
  * Named and parameterized piece of program
* Conditionals - If statements
  * Permit you to choose between paths
* Repetition
  * Do the same thing again and again
  * PB&J - untwist lid
  * Built-in repetition - + or <=

/Repetition/

* Repeat some action again and again and again
* Ask a question until a student gives a good answer
* PB&J example above
* (<= a b c d e f g)
  Check if a is less or equal than b,
  then if b is less than or equal to c,
  etc.
* For each student in the class, compute a letter grade

* In Scheme, the most common repetition is "for each element in a list"

/Recursion - Common Form of Repetition/

* Key idea: Repeat by having a procedure call itself.
(define average
  (lambda (a b c)
    (/ (+ a b c) 3)))

(define proc
  (labmda (...)
     ..
    (proc ...)))

Simple example: Length of a list
Can we write length ourselves?
Strategy:
(1) Pick a situation in which the answer is obvious, and use that
  as a part of your solution.
(2) Assume that you can solve the problem for a slightly simpler parameter
  (e.g., (cdr lst)), and use that to solve the whole problem

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

(len null)
=> 0

(len (cons 1 (cons 2 (cons 3 null))))
=> (+ 1 (len (cdr (cons 1 (cons 2 (cons 3 null))))))
=> (+ 1 (len (cons 2 (cons 3 null)))))
=> (+ 1 (+ 1 (len (cdr (cons 2 (cons 3 null))))))
=> (+ 1 (+ 1 (len (cons 3 null))))
=> (+ 1 (+ 1 (+ 1 (len (cdr (cons 3 null))))))
=> (+ 1 (+ 1 (+ 1 (len null))))
=> (+ 1 (+ 1 (+ 1 0)))

There are multiple ways to think about what's going on in recursive
procedures:

(define largest-of-list 
  (lambda (numbers)
    ; If the list has only one element
    (if (null? (cdr numbers))
        ; Use that one element
        (car numbers)
        ; Otherwise, take the greater of 
        ;  (a) the first element of the list
        ;  (b) the largest remaining element
        (max (car numbers)
             (largest-of-list (cdr numbers))))))

(largest-of-list (list 4 2 8 5 6 0))
=>... (max 4 (max 2 (max 8 (max 5 (max 6 (max (list 0)))))))

* We just assume that the recursive call works, and see what we
  should do with it.  (How mathematicians induce).
* In things like the first sum and the first largest-of-list,
  we 
  * first scan through to the end of the list, building up a
    sequence of operations to do
  * then, compute the result from right to left, applying each
    procedure in turn