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