CSC151.02 2003F, Class 17: More Recursion (Wheee!)
Admin:
* Homework due (I think you've all turned it in already).
* Questions on the exam?
* Reading for Friday: Preconditions and Postconditions
* Note: If you don't get a significant amount of today's lab done today, we'll use tomorrow for it.
Overview:
* Patterns of recursion.
* Questions on the first recursion lab?
* closest-to-zero
* New recursion lab.
/What is recursion?/
* Recursion is defining a process in terms of itself.
* Start with a large problem and break it into a smaller problem.
* Build the solutions to the smaller problems back into a solution to the larger problem.
/A Pattern for Recursion/
(define recursive-procedure
(lambda (PARAM)
(if (SMALL PARAM)
BASE-CASE
(EXTEND (recursive-procedure (MAKE-SMALLER PARAM))))))
(define recursive-list-procedure
(lambda (lst)
(if (null? lst)
BASE-CASE
(COMBINE (car lst)
(recursive-list-procedure (cdr lst))))))
Another possible base-case-test
(if (null? (cdr lst))
Why? When you want to do something that involves every member of a list.
* Finding the largest element in a list.
(define recursive-list-procedure
(lambda (lst)
(if (null? (cdr lst))
(car lst)
(max (car lst)
(recursive-list-procedure (cdr lst))))))
* Adding all of the elements in a list.
(define recursive-list-procedure
(lambda (lst)
(if (null? lst)
0
(+ (car lst)
(recursive-list-procedure (cdr lst))))))
* ...
/An Application: Closest-To-Zero/
(define closest-to-zero
(lambda (lst)
(if (null? (cdr lst))
(car lst)
(min (abs (car lst))
(abs (closest-to-zero (cdr lst)))))))
Whoops ... doesn't work
Another attempt
(define closest-to-zero
(lambda (lst)
(if (null? (cdr lst))
(car lst)
(min (abs (car lst))
(closest-to-zero (cdr lst))))))
Whoops ... doesn't work
(define closest-to-zero
(lambda (lst)
(if (null? (cdr lst))
(car lst)
(closer-to-zero (car lst)
(closest-to-zero (cdr lst))))))
Morals?
* Test your procedures.
* Recursion can become easier if you write helper procedures
* Making notes as to common "patterns" often helps
Side note: Name at least two things wrong with Luis's shirt
* Luis is not an alum.
* Luis is only one person.
Other questions on recursion?
Time to start the second recursion lab (or ask for help piratizing).
Reese's joke of the day:
* "Scheme doesn't have any morals".
; 1. Follow Sam's guidelines from a few minutes ago.
(define tally-skips-1
(lambda (lst)
(if (null? lst)
0
(tally-skips-1-combiner (car lst)
(tally-skips-1 (cdr lst))))))
(define tally-skips-1-combiner
(lambda (val count-of-remaining-skips)
(if (eq? val 'skip)
(+ 1 count-of-remaining-skips)
count-of-remaining-skips)))
; 2. List the possible cases and think about each of them.
; (1) List is null
; (2) car of list is 'skip
; (3) car of list is not 'skip
(define tally-skips-2
(lambda (lst)
(cond
((null? lst) 0)
((eq? (car lst) 'skip) (+ 1 (tally-skips-2 (cdr lst))))
(else (tally-skips-2 (cdr lst))))))
; 3. Add a counter.
(define tally-skips-3
(lambda (lst)
(tally-skips-3-helper lst 0)))
(define tally-skips-3-helper
(lambda (lst counter)
(cond
((null? lst) counter)
((eq? (car lst) 'skip) (tally-skips-3-helper (cdr lst) (+ 1 counter)))
(else (tally-skips-3-helper (cdr lst) counter)))))