Here is an iterative example of a procedure computing the fibonacci sequence in SICP. The idea is:
(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?
Bot procedures produce correct result. However, the first one retains the relationship between a and b: a is Fib(i+1) and b is Fib(i) where i=n-count. The second method uses the first iteration to swap a and b around, thus introducing one redundant iteration. This can be seen by taking the trace of procedures:
> (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))))
> (trace fib-iter)
> (fib 3)
>(fib-iter 1 0 3)
>(fib-iter 1 1 2)
>(fib-iter 2 1 1)
>(fib-iter 3 2 0)
<2
2
> (define (fib-iter a b count)
(if (= count 0)
b
(fib-iter b (+ a b) (- count 1))))
> (trace fib-iter)
> (fib 3)
>(fib-iter 1 0 3)
>(fib-iter 0 1 2)
>(fib-iter 1 1 1)
>(fib-iter 1 2 0)
<2
2
What you actually want is something like this:
> (define (fib n)
(if (zero? n)
0
(fib-iter 0 1 (- n 1))))
(define (fib-iter a b count)
(if (zero? count)
b
(fib-iter b (+ a b) (- count 1))))
> (trace fib-iter)
> (fib 3)
>(fib-iter 0 1 2)
>(fib-iter 1 1 1)
>(fib-iter 1 2 0)
<2
2
Notice, there is one less iteration. However, I'm doing extra work in procedure fib.