\documentclass[twocolumn]{article}

\usepackage{fullpage}
\usepackage{palatino}

\begin{document}

\title{6.001 Tutorial 2}
\author{David Ziegler}
\date{September 20, 2004}
\maketitle

\section{Substitution Model}
The substitution model is a simple way of thinking about how
computation works in Scheme.  As usual, it's a bit of a lie, but we'll
correct the lie shortly.  The substitution model tells us what happens
when a combination is evaluated:

\begin{itemize}
\item Evaluate subexpressions (in any order)
\item If the first subexpression is a primitive (built-in)
  procedure, just apply it to the other values
\item Otherwise, substitute the \emph{values} of each subexpression
  for the parameters in the body of the procedure, and then evaluate
  the body
\end{itemize}

\begin{verbatim}
;; Returns the number of digits in n
(define (num-digits n)




(num-digits 2038)





\end{verbatim}

\section{Recursive/Iterative Processes}
We've seen recursive \emph{procedures}, functions that call
themselves (possibly indirectly).  All functions that are
self-referential are recursive.  A \emph{process} can be either
iterative or recursive.

\textbf{Iterative processes} are those where the value of the
recursive call is directly returned -- no operations are performed
after the call.  If the function is named \verb+foo+, the call will be
\verb+(foo ...)+ all by itself.

\textbf{Recursive processes} are those where the value from the
recursive call is operated on before returning -- these \emph{pending
operations} are what make the process recursive.  If the function is
named \verb+foo+, the call might be \verb+(- (foo ...) ...)+.

It's often straightforward to convert a recursive process into an
iterative process:

\begin{verbatim}
(define (sum-r a b)
  (if (= a 0)
      b
      (+ 1 (sum-r (- a 1) b))))

(define (sum-i a b)



\end{verbatim}

\section{Problems}
\begin{verbatim}
;; From last time:
;; Finds the remainder of x/y using
;; repeated subtraction
(define (remainder x y)
  (if (< x y)
      x
      (remainder (- x y) y)))
\end{verbatim}

\noindent Iterative or recursive?

\begin{verbatim}
;; Finds the quotient of x/y
(define (quotient x y)



\end{verbatim}

\noindent Iterative or recursive?

\newpage

\begin{verbatim}
;; Alternate implementation
(define (quotient x y)





\end{verbatim}

\noindent Iterative or recursive?

\begin{verbatim}
;; Predicate -- is x divisible by y?
(define (divides? x y)

\end{verbatim}

\noindent Iterative or recursive?

\begin{verbatim}
;; Predicate -- is p a prime number?
(define (prime? p)





\end{verbatim}

\noindent Iterative or recursive?

\newpage

\begin{verbatim}
;; Prints out the prime
;; factorization of n
(define (factorize n)











\end{verbatim}

\end{document}