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
* 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"
O * O
If we click on the third circle, we get
O * *
What about "yesterday"?
Admin
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)))))