sicp exercise 3.57

;; Exercise 3.57.  How many additions are performed when we compute the nth Fibonacci number using the definition of fibs based on the add-streams procedure? Show that the number of additions would be exponentially greater if we had implemented (delay <exp>) simply as (lambda () <exp>), without using the optimization provided by the memo-proc procedure described in section 3.5.1

(define numofsum 0)
(define (plus a b)
  (set! numofsum (+ 1 numofsum))
  (+ a b))

(define (reset)(set! numofsum 0))

(define (add-streams s1 s2)
  (stream-map plus s1 s2))

(define fibs
  (cons-stream 0
               (cons-stream 1
                            (add-streams (stream-cdr fibs)
                                         fibs))))

(newline)
(display (stream-ref fibs 0))(display " ")(display numofsum)(newline)
(display (stream-ref fibs 1))(display " ")(display numofsum)(newline)
(display (stream-ref fibs 2))(display " ")(display numofsum)(newline)
(display (stream-ref fibs 3))(display " ")(display numofsum)(newline)
(display (stream-ref fibs 4))(display " ")(display numofsum)(newline)
(display (stream-ref fibs 5))(display " ")(display numofsum)(newline)
(display (stream-ref fibs 6))(display " ")(display numofsum)(newline)
(display (stream-ref fibs 20))(display " ")(display numofsum)(newline)



(display "-------------")(newline)


(reset)
(define (fibo n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (plus (fibo (- n 1))
                 (fibo (- n 2))))))

(display (fibo 0)) (display " ") (display numofsum) (newline)(reset)
(display (fibo 1)) (display " ") (display numofsum) (newline)(reset)
(display (fibo 2)) (display " ") (display numofsum) (newline)(reset)
(display (fibo 3)) (display " ") (display numofsum) (newline)(reset)
(display (fibo 4)) (display " ") (display numofsum) (newline)(reset)
(display (fibo 5)) (display " ") (display numofsum) (newline)(reset)
(display (fibo 6)) (display " ") (display numofsum) (newline)(reset)
(display (fibo 20)) (display " ") (display numofsum) (newline)(reset)

;; Output:
;Loading "sicp_prob_03.57.scm"...
;0 0
;1 0
;1 1
;2 2
;3 3
;5 4
;8 5
;6765 19
;-------------
;0 0
;1 0
;1 1
;2 2
;3 4
;5 7
;8 12
;6765 10945
;... done