\documentstyle[12pt,simplemargins]{article}
\setallmargins{1in}
\begin{document}

{\noindent\bf\Large 1.}
Given the procedure \verb+f+ which generates a recursive process, fill
in the blanks in the definition of \verb+f-iter+ which computes the same
values as \verb+f+ but which generates an iterative process.

\begin{verbatim}
(define (f x)
  (if (null? x)
      1
      (+ 2 (f (cdr x)))))

(define (f-iter x)
  (define (loop y z)
    (if (null? y)
        <ea>
        (loop (cdr y) <eb>)))
  (loop <ec> <ed>))

<ea> = 
<eb> = 
<ec> = 
<ed> = 
\end{verbatim}

{\noindent\bf\Large 2.} Given these definitions:

\vspace*{-.1in}
\begin{verbatim}
(define (poly x) (- (* 3 x) (* (cube x) 4)))
(define (cube x) (* x x x))

(define (sine-r angle)
  (if (not (> (abs angle) 0.1))
      angle
      (poly (sine-i (/ angle 3)))))
\end{verbatim}

{\noindent\bf\large (a)} What are the orders of growth for space and time of
\verb+sine-r+? 

\vspace*{.75in}

{\noindent\bf\large (b)} Write an iterative version of \verb+sine-r+ called
\verb+sine-i+. What are the orders of growth for space and time of this
procedure? 

\newpage

{\noindent\bf\Large 3.}
One way to approximate an irrational number is to expand it as a
continued fraction and truncate the expansion after a sufficient number
of terms. Suppose \verb+n+ and \verb+d+ are procedures of one argument
(the term index) that return the $i^{th}$ numerator and denominator of
the terms of the continued fraction:

\vspace*{-.25in}
\begin{center}
\[
\frac{N_1}{D_1 + \frac{N_2}{\ddots + \frac{N_K}{D_K + 0}}}
\]
\end{center}

A procedure to approximate an irrational number up to $k$ terms is:

\begin{verbatim}
(define (cont-frac n d k)
  (define (cf i)
    (if (> i k)
        0
        (/ (n i) (+ (d i) (cf (+ i 1))))))
  (cf 1))
\end{verbatim}    

{\noindent\bf\large (a)} Does the above procedure result in an iterative or a
recursive process? Why?

\vspace*{.75in}

{\noindent\bf\large (b)} Write an procedure that results in the opposite
kind of process than the one above, i.e. if the one above is recursive,
write a procedure that results in an iterative process.

\end{document}



