University of Virginia, Department of Computer Science CS200: Computer Science, Spring 2004

Notes: Wednesday 4 February 2004

• I am out of town at a conference the rest of the week, so there is no class on Friday and no office hours on Thursday.
• Wednesday, 11 February: Problem Set 3. Please get started on this early (i.e., already!).
• Before 10 March: Read rest of GEB part I (Chapters 2-4 and 6-9, in addition to Chapters 1 and 5 you have already read). There will be no more specific reading assignments from GEB until end of Spring Break (there will be other reading assignments from SICP). By March 10th, you will be expected to have read all of Part I (through page 272) of GEB. I recommend reading about a Chapter a week, but if you prefer to read it all over Spring Break that is fine too.
Code
```(define (dofor proc start end)
(if (> start end)
null
(cons (proc start)
(dofor proc (+ start 1) end))))

(define (intsto n) (dofor (lambda (x) x) 1 n))

(define (dountil proc stoptest incr current)
(if (stoptest current)
null
(cons (proc current)
(dountil proc stoptest incr (incr current)))))

(define countdown
(dountil (lambda (x) x) (lambda (val) (< val 1)) (lambda (x) (- x 1)) 10))

(define (for index stoptest combine next accum)
(if (stoptest index)
accum
(for (next index) stoptest combine next (combine index accum))))

(define (gauss-sum n)
(for 1 (lambda (index) (<= index n)) + (lambda (x) (+ 1 x)) 0))

(define (fast-fibo n)
(first
(for
1                       ; initial iteration value
(lambda (i) (<= i n))   ; test - if it evaluates to true when applied to current iteration value, keep going
(lambda (accum i)       ; combiner function
(list (+ (first accum) (second accum)) (first accum)))
(lambda (i) (+ i 1))    ; next function
(list 0 1))))           ; initial accumulator value

```

Recursion is the root of computation since it trades description for time.
Alan Perlis