The process generated using the normal-order evaluation is the following. It performs 18 `remainder` operations: 14 when evaluating the condition and 4 in the final reduction phase.

(gcd 206 40) (if (= 40 0) ...) (gcd 40 (remainder 206 40)) (if (= (remainder 206 40) 0) ...) (if (= 6 0) ...) (gcd (remainder 206 40) (remainder 40 (remainder 206 40))) (if (= (remainder 40 (remainder 206 40)) 0) ...) (if (= 4 0) ...) (gcd (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))) (if (= (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) 0) ...) (if (= 2 0) ...) (gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))) (if (= (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))) 0) ...) (if (= 0 0) ...) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))

The number 'R' of `remainder` operations executed by the normal-order evaluation process is given by the formula

```
R = SUM(i from 1 to n, fib(i) + fib(i - 1)) - 1
```

where `n` is the number of `gcd` invocations required to compute the `(gcd a b)`. The first invocation does not need to compute `remainder` thus the `-1`

`R` is given by the following function:

```
(define (count-remainders n)
(define (loop n sum)
(if (= 0 n) (- sum 1)
(loop (- n 1) (+ sum (fib n) (fib (- n 1))))))
(loop n 0))
```

In this particular case that is:

```
(count-remainders 5)
=> 18
```

The process generated using the applicative-order evaluation is the following. It performs 4 `remainder` operations.

(gcd 206 40) (gcd 40 (remainder 206 40)) (gcd 40 6) (gcd 6 (remainder 40 6)) (gcd 6 4) (gcd 4 (remainder 6 4)) (gcd 4 2) (gcd 2 (remainder 4 2)) (gcd 2 0) 2

<< Previous exercise (1.19) | sicp-solutions | Next exercise (1.21) >>