CSC151, Class 15: Repetition with Recursion

Overview:
* Reflection on CGI
* Repetition
* Recursion as a design technique
* An Example
* Recursion in Scheme

Notes:
* Read: Repetition with Recursion 
  for more details about the subject of today's class.
* Today's class will be held in lecture + discussion format.
* Are there questions on homework 2?

----------------------------------------

Question 1: What did you learn (in this class) on Monday 
and Tuesday?

* Buzzword buzzword buzzword through buzzword buzzword
  buzzword
* Some tenuous way to relate Scheme to HTML using CGI.
* Sam can't write instructions, which is really sad given
  that his discipline focuses on writing instructions
* Low-level thing: To create a field in which the user
  can type something, use the following HTML
<input type="text" name="...">
* In writing Scheme programs that try to use those values,
use
  (get-cgi-variable 'name-of-variable "some default value")
* Changes have to happen all over the place
  (1) In your HTML page.
  (2) In the body of the page procedure, which calls some
      other procedure
  (3) In the called procedure
* Don't forget to save and reload.  Old versions have a
  nasty habit of sticking around.
* How to make "circle checkbox radio buttons"
<input type="radio" name="fred" value="1">
<input type="radio" name="fred" value="2">
<input type="radio" name="wilma" value="3">

O * O

If we click on the third circle, we get

O * *

What about "yesterday"?
<input type="radio" name="status" value="administrator">Admin
<input type="radio" name="status" value="student">Student

------------------------------------------------------------

Observation: Many algorithms involve doing things multiple
times.
* Either a fixed number of times
* Or until a condition holds.

Lots of ways to express repeat:

1 Stir the stuff once
2 If you haven't stirred it fifty times, go back to step 1

1. Stir the stuff fifty times

Schemes's model of repetition: 
* Do something once
* Do it the remaining times
* Combine your results

Easiest way to look at this mechanism is to solve some
problems (in English first)

* Given a list of integers, find the largest integer in
  the list
* Given a list of integers, find their sum.
* Given a symbol and a list of symbols, determine if the
  symbol appears somewhere in the list.

Find the largest in a list:
* Take the car of the list
* Take the car of the cdr
* Take the largest of the two
* Compare to the car of the car of the cdr

Keep track of the largest element, and compare it to
each element in the list in turn, choosing the larger
at each step

(21111 21 0 56 3  2 1 2 2332 1 3 45 2 1 4)
Find the largest element in the cdr of the list.a

(largest (21 0 56 3  2 1 2 2332 1 3 45 2 1 4)) => 2332
The largest element in the whole list is the larger of
the car and the largest of the remaining.

Let's express this in Scheme.

(1) How do we find the larger of two values?
(define larger
  (lambda (a b)
    (if (< a b) 
        b
        a)))

------
STUFF FROM DRSCHEME

; Citation: larger written by Sarah Fullmer
(define larger
  (lambda (a b)
    (if (< a b)
        b
        a)))

(define larger2 max)

; The largest thing in a list is the larger of
; (a) The first thing
; (b) The largest remaining thing
; Whoops!  The largest thing in a one element list is that
; thing.
(define largest
  (lambda (lst)
    ; If the list has only one element
    (if (= (length lst) 1)
        ; Use that one element
        (car lst)
        ; Otherwise, do what we said above
        (larger (car lst)
                (largest (cdr lst))))))

; How does DrScheme evaluate
; (largest (list 1 55 2 3))
; => (larger 1 (largest (list 55 2 3)))
; => (larger 1 (larger 55 (largest (list 2 3))))
; => (larger 1 (larger 55 (larger 2 (largest (list 3)))))
; => (larger 1 (larger 55 (larger 2 3)))
; => (larger 1 (larger 55 3))
; => (larger 1 55)
; => 55

; AGH!  We're defining largest based on largest!
; The model of recursion: Define things in terms of themselves.

; How does recursion work?
; (1) Each time you call the procedure, you must 
;     *simplify* the parameter.
; (2) Eventually, you must reach a point at which you can
;     just answer the question.
; (3) You need a way to use the answer to the simpler 
;     problem to solve the more complex problem.

; Cite: Andy Cook's method, as adjusted by many helpful
; colleagues in CSC151.02
;   Assume the larger of the first two things is the largest
;   Step through the list until we reach then end, 
;     updating our guess as we go.
(define new-largest
  (lambda (lst)
    (largest-helper lst (larger (car lst) (cadr lst)) 2)))

(define largest-helper
  (lambda (lst largest-so-far position)
    ; If we run off the end of the list, use the largest-so-far
    (if (>= position (length lst))
        largest-so-far
        ; Otherwise, update your guess and continue
        (largest-helper lst 
                        (larger largest-so-far 
                                (list-ref lst position))
                        (+ position 1)))))