How many additions are performed when we compute the $n^{th} $ 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.

(define fibs
	(cons-stream
		0
		(cons-stream 1 (add-streams (stream-cdr fibs) fibs))))
	
(define (memo-proc proc)
	(let ((already-run? false) (result false))
		(lambda ()
			(if (not already-run?)
				(begin (set! result (proc))
							 (set! already-run? true)
							 result)
				result))))
				
(define (add-streams s1 s2) (stream-map + s1 s2))

He who forget

on the first sight, if you simply draw a graph like below (like I do), this question would be very confusing. shouldn’t It be like this? isn’t the number of addition is always $n-2$ whether we apply memo-proc ?

      fibs: 0  1  1  2 ...
  cdr fibs: 1  1  2  3 ...
            +  +  +  +
fibs: 0  1  1  2  3  5 ...

well, for the evaluation result, it’s right, but wrong when it comes to how it is evaluated.

let’s expand it a little bit.

fibs = [0, 1, add fibs fibs.next] ;; for simplcity, rewrite fibs

;; expand till the third value can be evaluated
fibs = [0, 1, add [0, 1, add fibs fibs.next] [1, add fibs fibs.next]]
;; progress the otter 'add' of the third item (r shift for one item)
fibs = [0, 1, 1, add [1, add fibs fibs.next] [add fibs fibs.next]]

wow, the third value comes out as 1. and it’s obvious that it takes one add operation because we change one add. keep up for the forth value.

;; add fibs fibs.next <=> 1, add [1, add fibs fibs.next] [add fibs fibs.next]
;; above transformation equivalent and takes one add operation
fibs = [0, 1, 1, add [1, add fibs fibs.next] [1, add [1, add fibs fibs.next] [add fibs fibs.next]]]
fibs = [0, 1, 1, 2, add [add fibs fibs.next] [add [1, add fibs fibs.next] [add fibs fibs.next]]]

;; make a variable
f+ = [add fibs fibs.next]
fibs = [0, 1, 1, 2, add f+ [add [1, f+] [f+]]]

;; the first item in f+ is 1, and it is evaluated for two times
;; which brings two add operation
;; fibs = [0, 1, 1, 2, add f+ [add [1, f+] [f+]]]
;;                         ^                ^
;; plus two add should be performed to make the value move to otter space
;; fibs(4) = 3, A(4) = 2+2 = 4

;; so on and so forth

see, we not ‘remember’ each item, instead, each item is decomposed till reach fibs[0] and fibs[1].

for a general case w/o memo-proc, let $A(n)$ be the number of addition for the $n^{th}$ fibs, there is,

$$ A(n) = A(n-1) + A(n-2)+1,\ where~A(0) = 0,\ A(1)=0 $$

$A(2) = A(0) + A(1)+1 = 1$

$A(3) = A(1) + A(2)+1 = 2$

$A(4) = A(2) + A(3)+1 = 4$

$…$

and it will end up result to, in which k is the exponential base.

$$ k^{n-2}>\phi^{n-2},\ where\ \phi=\frac{\sqrt{5}+1}{2} $$

He who memo

the memo version does exactly the one at the very beginning

      fibs: 0  1  1  2 ...
  cdr fibs: 1  1  2  3 ...
            +  +  +  +
fibs: 0  1  1  2  3  5 ...

however, the question is, how the hack does scheme remember it? where does it preserve the value?