CS 37

Clab 2: Recursion and Fun with graphics

; in definition window (define fact (lambda (n) (cond ( (= n 0) 1) (#t (* n (fact (- n 1)))) ) ) ) ;in interaction window try (fact 3) (fact 5) Put (fact 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 pull down the Language menu and change to Pretty Big under PLT). Then select run.

; in definitions window type (require (lib "trace.ss")) ; and if not there, put in the definition for fact (copy and paste or type) ;and click on run ;now try in interactive window (fact 4) ;now in interactive window (trace fact) ;and then (fact 4) ; this shows every time fact was called with its argument ;and what it returned (sometimes much lower). I'll ;annotate. Make sure you understand the output. > (fact 4) ; initial call to fact in interactive window |(fact 4) ;trace showing that fact is invoked with arg 4 | (fact 3) ;trace showing that fact is invoked with arg 3 ;before anything is returned from (fact 4) | |(fact 2) | | (fact 1) | | |(fact 0) ;trace showing that fact is invoked with arg 0 | | |1 ;trace showing value returned from (fact 0) | | 1 | |2 | 6 ;trace showing value returned from (fact 3) |24 ;at long last return from (fact 4) by trace 24 ;the value returned by REPL ;try (trace * -) (fact 4) ; it can get kind of ugly. So use trace when you need help. ; so now do (untrace fact - *) ; and (fact 7) ; to see that trace is really turned off. If you are getting concerned about defining valuable procedures and having them disappear when you are finished, just select save definitions as from the File menu. Save often.

Now for some fun!!

Get a new DrScheme window from the file menu.
Click the Run button. Pull down the help desk and search for viewport.
Click on 'viewport in "Viewport Graphics" '
Then skim over the contents of the first few commands on the pages Basic Commands, Position Operations, Color Operations, Lines, Ellipses.

In the definitions window put:

(require (lib "graphics.ss" "graphics")) (open-graphics) (define win1 (open-viewport "cfk1" 500 500)) (define win2 (open-viewport "cfk2" 200 400)) Press Run. Two viewports should come up. Using your mouse, drag them around so that you can see them and your DrScheme window. Then in your DrScheme interactions window, try: > ((draw-line win1) (make-posn 100 100) (make-posn 300 400)) > ((draw-line win2) (make-posn 10 100) (make-posn 30 40)) > ((draw-solid-ellipse win1) (make-posn 20 300) 30 30 (make-rgb 1 0 0)) I'll say a few words about what we are doing. If you are ahead, start playing around with graphics commands. These graphics commands are not part of the Scheme standard. So do not waste mental effort to memorize them. You can look them up (using help) when you need them.

A couple of more useful commands are:

> (close-viewport win2) > ((clear-viewport win1)) > (close-graphics) >

I want to be able to work in the window that is called win1 internally and I don't want all the overhead of make-posn, and make-rgb, etc. So I am going to define some procedures to make life easy on myself. The name of the viewport should be a parameter. But to save typing, I am being lazy and hard-coding it.

;;; draw a blue line from one point with Cartesian coordinates ;;; (x1, y1) to another point with coordinates (x2, y2) in window ;;; win1 (define bdraw-line (lambda (x1 y1 x2 y2) ((draw-line win1) (make-posn x1 y1) (make-posn x2 y2) (make-rgb 0 0 1)))) Use bdraw-line to draw a couple of lines.

Suppose you want to draw two lines of equal length that meet at a right angle and such that the unattached end point of one is (x1, y1) and the unattached endpoint of the other is (x2, y2). That is, we want to draw the two legs of an isosceles right triangle whose hypotenuse is the straight line from (x1, y1) to (x2, y2). We can do this by finding the coordinates of the right angle vertex, call them (xm, ym), and then drawing a line from (x1, y1) to (xm, ym) and another line from (xm, ym) to (x2. y2). There are actually 2 possible vertices (xm, ym) that will work, one on each side of the hypotenuse. Using a little math and a lot of algebra, one possible set of coordinates are xm=(x1+x2+y1-y2)/2 and ym=(x2+y1+y2 -x1)/2 (trust me). Let's define an operator to draw the two legs.

;;; two-legs draws the two legs of the isosceles right triangle whose ;;; hypotenuse is the line from (x1, y1) to (x2, y2) (define (two-legs x1 y1 x2 y2) (define (lines-to xm ym) ;;;lines-to actually draws the lines given the (bdraw-line x1 y1 xm ym) ;;;coordinates of the right angle vertex (xm, ym) (bdraw-line xm ym x2 y2) ) (lines-to ;;;invoke lines-to with the (/ (- (+ x1 x2 y1) y2) 2) ;;;argument for xm and (/ (- (+ x2 y1 y2) x1) 2) ;;;argument for ym ) ) Try it out by clearing the graphics screen and entering: (bdraw-line 50 50 100 150) ;;;draw a hypotenuse and then: (two-legs 50 50 100 150) ;;;draw the two legs Of course you can draw the two legs without drawing the hypotenuse. Try it for a few values.

If you are getting concerned about defining valuable procedures and having them disappear when you are finished, just select save definitions as from the File menu. Save often.

There is a kind of fractal curve called a C curve. A level 0 C curve is a straight line. A level n C curve consists of two level n-1 C curves meeting at a right angle such that the unattached endpoints of the level n-1 C curves are the endpoints specified for the level n C curve. Our procedure bdraw-line draws a level 0 C curve. Our procedure two-legs draws a level 1 C curve. We could try and write new procedures for level 2 C curves, then another for level 3, .... But that would be pretty concrete and we are studying procedural abstraction, so ....

;;; c-curve draws a C curve of level specified by the argument in level ;;; from (x1, y1) to (x2, y2) (define (c-curve x1 y1 x2 y2 level) (define (curves-to xm ym) ;;;draws the lower level curves to mid vertex (c-curve x1 y1 xm ym (- level 1)) ;;; whose coordinates are (xm, ym) (c-curve xm ym x2 y2 (- level 1)) ) (if (= level 0) (bdraw-line x1 y1 x2 y2) ;;; level is 0 so just draw a straight line (curves-to (/ (- (+ x2 x1 y1) y2) 2) ;;;level is greater than 0 so pass the coord (/ (- (+ x2 y1 y2) x1) 2) ;;;of mid vertex to curves-to ) ) )

Now get a new graphics window and then without clearing the graphics window in between, execute:

(c-curve 250 100 350 300 0) (c-curve 250 100 350 300 1) (c-curve 250 100 350 300 2)

Now add (require (lib "trace.ss")) to the definitions window and hit run. Then in interaction window, type

(trace c-curve bdraw-line)

Then execute in a clear graphics window

(c-curve 250 100 350 300 0)

Then execute in a clear graphics window

(c-curve 250 100 350 300 1)

Then execute in a clear graphics window

(c-curve 250 100 350 300 2)

Make sure you understand the curve drawn and how it relates to the output of the trace. Call Janis or me over if you have questions.

Now for your reward.

(untrace bdraw-line c-curve) (c-curve 250 100 350 300 13) Actually drawing a level 15 on level 11 or a level 4 on level 3 is fun too.

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 run ;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 Janis or 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.

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.