\documentstyle{article}

\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\topmargin}{0.0in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.4in}
\setlength{\parindent}{0in}
\setlength{\parskip}{0.12in}

\begin{document}

\newcommand{\bfs}[1]{{\bf #1}}

\begin{center}
{\LARGE\bf Recursion:  Example I

\end{center}

\bigskip

In languages in general, we say a procedure or function is \bfs{recursive}
if it calls itself.  The C language does allow recursion (as does Pascal).
For some languages, such as LISP, recursion is actually a major theme.

Many of the Unix ``commands'' (keep in mind that these are of course
{\it programs}, which someone wrote) are also recursive.  From example,
\bfs{rm}, the Unix remove-file command, has a -r option which is recursive:
If one of the files being removed is a directory, and this option is used,
then the \bfs{rm} will be applied to all files within that directory, and
all subdirectories, sub-subdirectories, and so on.  (The \bfs{cp} command
has a similar option.)

In some applications, use of recursion can lead to a strikingly compact
and elegant solution to what may seem to be an otherwise-insurmountable
problem.

The basic idea of writing a recursive function is as follows:

\begin{quote}
{\bf Supppose one has a task from some broad category.  Break that
task down into one or more new tasks which are of that same category.
Write the function to do this category of tasks as consisting partly of
one or more calls to itself, with those calls being for performing the
new tasks.}
\end{quote}

Our first example of recursion is to implement {\it Quicksort}, a technique
for sorting an array of elements in smallest-to-largest order.  In this
case, the ``category'' is sorting.  The breaking down of tasks is as
follows.

For concreteness, suppose the array to be sorted consists of

\begin{verbatim}
   12   5   66   13   8   35   29   88
\end{verbatim}

Let us choose the first element, 12, as our {\bf pivot element}.
Now, form two subarrays, consisting of all those original array
elements which are smaller than, and larger than the pivot element,
respectively:

\begin{verbatim}
   smaller:   5   8   
\end{verbatim}

\begin{verbatim}
   larger:   66   13   35   29   88
\end{verbatim}

So now we are faced with two new tasks ``of the same category,'' i.e. the
sorting category, as the original one---sorting the smaller list, and
sorting the larger list.  So, let's sort them:

\begin{verbatim}
   smaller:   5   8
\end{verbatim}

\begin{verbatim}
   larger:   13   29   35   66   88
\end{verbatim}

Now string together three items---the smaller array; the pivot element;
and the larger array:

\begin{verbatim}
   5    8   12   13   29   35   66   88
\end{verbatim}

Now our \underline{original} array is sorted!  The key point was that
the all the elements in the smaller array were smaller than the 12,
and all the elements in the larger array were larger than the 12---so
we naturally get the correct order by merely stringing these three
arrays together.

Below is a recursive function to do Quicksort, along with a main program
and data with which to test it.  The implementation here has been chosen
for the sake of clarity, not efficiency.  The one available in the C
library is more efficient (use of this function will be discussed in
another handout).

\begin{verbatim}
  1  Script started on Wed May  6 13:19:52 1992
  2  heather% cat Q*
  3  
  4  
  5  /* function QuickSort(), and program to test it */
  6  
  7  
  8  int X[100],  /* test array */
  9      N;  /* length of X */
 10  
 11  
 12  /* function to do a quick-sort of integers; note that both this
 13     version and the one in the text are recursive, but the one here 
 14     has sacrificed efficiency and generality for clarity */
 15  
 16  void QuickSort(IntArray,N)  /* sort the IntArray array of N elements */
 17     int IntArray[100],N;
 18  
 19  {  int Smaller[100],Bigger[100],ComparisonValue,SmallJ,BigJ,I;
 20  
 21     if (N <= 1) return;  /* array nonexistent or already sorted */
 22  
 23     /* idea: put all the elements smaller than IntArray[0] into
 24        the array Smaller, and all the ones bigger than IntArray[0]
 25        into the array Bigger; then sort Smaller and Bigger; then
 26        put it all back together again into the big array IntArray */
 27  
 28     ComparisonValue = IntArray[0];
 29     SmallJ = BigJ = 0;
 30     for (I = 1; I < N; I++)  {
 31        if (IntArray[I] <= ComparisonValue)
 32          Smaller[SmallJ++] = IntArray[I];
 33        else
 34          Bigger[BigJ++] = IntArray[I];
 35     }
 36  
 37     /* at this point there are SmallJ values in the array Smaller,
 38        and BigJ values in the array Bigger; now sort them */
 39  
 40     QuickSort(Smaller,SmallJ);
 41     QuickSort(Bigger,BigJ);
 42  
 43     /* put it all together now, exploiting the fact that all the
 44        elements in Smaller are smaller than ComparisonValue, and
 45        all the elements in Bigger are bigger than it */
 46     for (I = 0; I < SmallJ; I++) IntArray[I] = Smaller[I];
 47     IntArray[SmallJ] = ComparisonValue;
 48     for (I = 0; I < BigJ; I++) IntArray[SmallJ+1+I] = Bigger[I];
 49  
 50     /* done; IntArray is now in order */
 51  }
 52  
 53  
 54  main()
 55  
 56  {  int I,Tmp;
 57  
 58     printf("enter array, with ctrl-d to end\n");
 59     for (N = 0; ; N++)  {
 60        if (scanf("%d",&Tmp) == -1) break;
 61        X[N] = Tmp;
 62     }
 63     QuickSort(X,N);
 64     printf("sorted array:\n");
 65     for (I = 0; I < N; I++) printf("%d\n",X[I]);
 66  }
 67  
 68  
 69  
 70  heather% cc -g Q*
 71  heather% a.out
 72  enter array, with ctrl-d to end
 73  124 22 10 195 200 15 6 99 166
 74  sorted array:
 75  6
 76  10
 77  15
 78  22
 79  99
 80  124
 81  166
 82  195
 83  200
 84  heather% e
 85  heather% 
 86  script done on Wed May  6 13:21:02 1992
\end{verbatim}

\bfs{Analysis:}

The function basically follows the outline mentioned above, i.e.
forming the two subarrays, sorting them, and then putting the results
together.  A couple of points need to be mentioned, though:

\begin{itemize}

\item  In any recursive function, there is some special case of the
task which is handled directly, rather than via further calls.  In
the example here, that special case is checked on Line 21.  This is
what makes a set of recursive calls eventually terminate.  Here, for
instance, there will be more and more calls, each one of which splits
the current array into two subarrays, etc., so eventually these calls
will be on subarrays consisting of only one element; when that happens,
Line 21 will ensure that no further calls are made.  These considerations
should be kept in mind when you are {\it debugging}.

\item On the other hand, at the time you are {\it writing} the program,
you should \underline{not} think about the continuing sequence of calls
which actually get made; you should only think about how to convert the
original task into one or more smaller tasks.

\end{itemize}

\end{document}