CS 22

Clab 3: Recursion, Iteration, some lists

Put DrScheme in beginner mode. ; in definition window (define (factrec n) (if (= n 1) 1 (* n (factrec (- n 1))))) (define (factorial n) (fact-iter 1 1 n)) (define (fact-iter product counter max-count) (if (> counter max-count) product (fact-iter (* counter product) (+ counter 1) max-count))) ;press execute ;put (factrec 4) in the definition window and invoke step ;keep steping watching the action. Make sure you understand ;what is happening. Call me over if you have questions. ;Now delete (factrec 4) from the definition window and replace ;it with (factorial 4) and invoke step ;keep steping watching the action. Make sure you understand ;what is happening. Call me over if you have questions. ;compare and contrast factrec with fact-iter.
Now in one drscheme window, define fibrec as the text does on page 37 (define (fibrec n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (fibrec (- n 1)) (fibrec (- n 2)))))) and in a second drscheme window, define fib and fib-iter as text on page 39. (define (fib n) (fib-iter 1 0 n)) (define (fib-iter a b count) (if (= count 0) b (fib-iter (+ a b) a (- count 1)))) Invoke step on (fibrec 6) then on (fib 6). Put the stepper windows side by side and compare and contrast. You should understand what is happening and how they differ. If you do not, discuss with your neighbor and/or call me over. After you have stepped enough to see what is going on in each version, click the home button and then do 20 steps in each window. Consider what a time-sharing operating system would have to remember in order to restart each computation assuming it had to stop each and swap them out of main memory. Consider the relative space and time efficiency of these two alternative methods to compute fibonacci numbers.

Another way to appreciate the difference is to start (fibrec 30) in the interaction window with fibrec then go over to the window with fib and start (fib 30). Do that now and note how much faster the iterative process finishes compared to the recursive process.

In order to focus on procedural abstraction, your authors work only with numbers in chapter 1. I want to be able to talk about some other applications and therefore want to introduce the built-in data structure, list, now. So... Please skim over the following material from online help: the first 3 screens worth of section 6.3.2 under R5RS (get by searching for car then click on (car pair) then scroll to top of page), then read about quote, cons, car, cdr, list, equal?, null? in R5RS. Don't worry if you do not understand everything. If you happen to see set-car! or set-cdr!, turn away fast! These are examples of GROSS-LISP and we are trying to work in almost-Pure-Lisp for the time being . Define some lists and try applying these functions. I'll say a few words in class about lists.

Change your language level to Full Scheme. Now try evaluating each of the following. Make sure you understand the result you get. Ask questions if you have them.

a 'a (define a '(cat dog amt)) a 'a (car a) (cdr a) (cons 'horse a) a (define b '(horse dog)) a b (cons a b) (car (cdr a)) (define c '(dog horse)) (define d '(horse dog)) a b c d (equal? a b) (equal? b d) (equal? c d) ;;; note that order counts in ;;; list equality. (eq? b d) ;;; note eq? is different than equal? For now use equal? (cdr (cdr d)) (cddr d) ;;; short hand for (cdr (cdr d)) (cons 'fun '()) (null? (cdr d)) (null? (cddr d)) Recall that when we cons'd two lists, the entire first list became one of the elements of the result instead of the individual elements of the first list becoming elements of the result. Frequently, we want the latter result. In fact, there is a built-in function to achieve that called append. But in order to understand this better, we will write our own. ;;; app assumes that both arguments x and y are lists. The result is a new ;;; list consisting of the elements of x followed by the elements of y. (define (app x y) (cond ((null? x) y) ;;; if x is empty, return y (else (cons (car x) (app (cdr x) y))) ;;;otherwise, ;;; return the first element of x ;;; cons'd to the result of app applied to ;;; the rest of x and y ) ) Now evaluate: a b (cons a b) (app a b) Put (require-library "trace.ss") in the definitions window and press execute. Now put trace on for car, cdr, cons, and app and evaluate (app a b) making sure you understand the output of the trace. Ask questions if you have them.

That's it for today. If you got this far, that's wonderful. If you didn't, don't worry. We are not in a race. Finish up at home and ask me questions next time if you have them. This is great stuff and will hopefully help you understand your reading.

Have a nice weekend.
Don't forget your homework for Monday.
email me text solutions by class time.