chong.franklin
2/28/2016 6:37:00 PM
Here is an iterative example of a procedure computing the fibonacci sequence in SICP. The idea is:
<ul>
<li>a = fib(n+1) = a+b</li>
<li>b = fib(n) = a</li>
</ul>
(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))))
Looking at it deeper, I don't understand why continuing the computation towards fib(n+1) is necessary. I found we could have written.
;; a and b are first and second integers respectively
;; in the recursive call, b would be replaced by a+b because it is the next number in the sequence
;; so now a will be replaced by the previous value of b because it is the previous value.
(define (fib2 n)
(fib-iter 1 0 n))
(define (fib-iter a b count)
(if (= count 0)
b
(fib-iter b (+ a b) (- count 1))))
Now, I really think the first example, the one continuing up to n+1 is really redundant. I don't understand why is that necessary. What's wrong with my proposed iterative example?