sol-1.20.tex

\def\steps#1{\hskip\ttindent\,\,{\typoscale[1400/]$\downarrow$}{\typoscale[850/]\quad$#1$\ evaluation\ifnum#1=1\else s\fi\ of \code{remainder}}}%
If we interpret the procedure $\mathop{\rm GCD}$ using normal-order evaluation, when evaluating the expression `(gcd 206 40)`, we generate the following process:
\begtt\scm
(gcd 206 40)
\endtt
\steps0
\begtt\scm
(gcd 40 (remainder 206 40))
\endtt
\steps1
\begtt\scm
(gcd (remainder 206 40)
     (remainder 40 
                (remainder 206 40)))
\endtt
\steps2
\begtt\scm
(gcd (remainder 40
                (remainder 206 40)) 
     (remainder (remainder 206 40)
                (remainder 40 
                           (remainder 206 40))))
\endtt
\steps4
\begtt\scm
(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)))))
\endtt
\steps7
\begtt\scm
(remainder (remainder 206 40)
           (remainder 40
                      (remainder 206 40)))
\endtt
\steps4
\begtt\scm
2
\endtt
Each time that $\mathop{\rm GCD}$ is applied, its second argument must be evaluated in order to test if it is zero. In total the process performs $18$ `remainder` operations.

Instead, if we use applicative-order evaluation, we need to perform only $4$ `remainder` operations.