Copyright (C) 1997 Rich Neidinger, John Swallow, and Todd Will.  Free for
distribution to college and university instructors for personal,
non-commercial use.  If these notebooks are used in a course, the authors
request $20 per student.

16. Recursion I:  Passing the Buck

Last revision:  October 23 1996

In this section we consider in more depth the programming style mentioned
several times previously, recursion.  We define base cases and discuss how
a recursive definition must implicitly assume that the function works
correctly for smaller, or simpler, values of the parameter.  We conclude
with good examples of recursion, as well as examples of programming styles
which do not incorporate recursion.

Recursion

The Religion of Recursion:  Passing the Buck

A recursive function is a function which accomplishes a programming task by
repeatedly invoking, or calling, itself.  The example of recursion which we
have encountered several times before is the factorial function:

Clear[fac]
fac[1]=1;
fac[n_Integer /; Positive[n] ] := n fac[n-1]
fac[7]

In the definition of the function "fac[ ]" we find a function call to "fac[
]", which distinguishes this function as recursive.

Recursive functions differ from other functions in the way they break a
programming task into smaller steps.  The functions which we have
previously encountered used commands such as "Table[ ]" and "Map[ ]" to
repeat one operation over and over.  Instead of using such pre-defined
commands to implement repetition, however, recursive functions accomplish a
sequence of smaller steps by either (a) performing one small operation and
then invoking themselves again, or (b) invoking themselves again and then
performing one small operation.  Since one operation is accomplished with
every invocation of the function, and since the function invokes itself
repeatedly, the many small operations which make up the programming task
are eventually accomplished.  In the factorial function above, the
recursive call is of the second type, where the function invokes itself and
then performs the small operation.  What happens is that "fac[n]" invokes
"fac[ ]" again with a smaller parameter, "n-1", and once the result is
completed, the small operation is performed:  the result of "fac[n-1]" is
multiplied by "n".

Let us step through the action of "fac[ ]" so that we see clearly the
successive, nested function calls.  We consider the action
anthropomorphically.  When we enter "fac[7]", "fac[ ]" says, "I don't want
to do all this work.  I'll pass most of the burden on to fac[6].  I'll just
multiply whatever fac[6] gives me by 7."  Then execution for "fac[7]" is
halted, while "fac[7]" waits for the result from "fac[6]".  When "fac[ ]"
is called with a parameter of "6", it says, "I don't want to do all this
work, let me get that lackey fac[5] to do most of the work, then I'll just
multiply by 6."  Then execution for "fac[6]" is halted, waiting on the
result of "fac[5]".  In turn, "fac[5]" gets the underling "fac[4]" to do
most of the work, and so on.   All of this buck passing finally comes to a
end with "fac[1]", who has no assistants to turn to.  But "fac[1]" has a
special definition:  "fac[1]=1".  Hence "fac[1]" returns a 1, and "fac[2]"
resumes execution, taking this result, 1, and multiplying by 2.  Then
"fac[3]" resumes execution, taking the result of "fac[2]", namely 2, and
multiplying it by 3, and so forth.  Finally "fac[7]" takes the result of
"fac[6]", namely 720, and multiplies by 7, yielding the final answer, 5040.

Base Cases; Simplifying until the Base Case Holds

From studying the function's repeatedly invoking itself, it should be clear
that having a special case, where "fac[1]=1", was very important;
otherwise, "fac[ ]" would have passed the buck an infinite number of times!
This sort of special case for a recursive function, in which a fixed
return value is specified for a particular value of the parameter, is
called a base case.  Our function "fac[ ]", then, has a base case when the
value of the parameter is equal to 1, and the result of the base case is to
return the integer 1.

Typically, recursive functions operate by simplifying the parameter(s) and
then invoking themselves again with a simpler parameter value, where the
meaning of "simpler" depends on the parameter type.  For instance, if the
parameter values are positive integers, as in the case above, a simpler
parameter value would be a smaller, positive integer.  On the other hand,
if the parameter values are lists, then a simpler parameter value might be
a list with fewer elements.  The value of the function for the base case is
thus defined to be the result when the parameter is the simplest possible.
Again, since the recursive function repeatedly simplifies the parameter,
the process of buck-passing is destined to stop, since the simplest
possible case, the base case, will ultimately be reached.  In the factorial
function, the simplest possible case is when the parameter value is a 1.

Writing Recursive Functions

In practice, when writing a recursive function, it is usually best to work
from the bottom up, which here means that one should define the base case
first.  In other words, decide what values the parameter should allow, the
way in which the parameters might become simpler, and what the simplest
possible case would be.  Then write the definition of the recursive
function, which must, somewhere in its definition, invoke itself with a
simpler version of the parameter.  When defining the recursive function,
one must have faith that the function will perform correctly for simpler
parameters; the job of the function is only to perform a small operation
and invoke the function again with a simpler parameter.

Let us consider this process, applied to the factorial function above.  We
would first decide that the factorial function takes positive integer
parameters, the simplest of which would be the smallest positive integer,
namely 1.  Next, we would define the base case:  "fac[1]=1".  Finally, we
would consider what small operation "fac[ ]" should perform, assuming that
"fac[ ]" applied to a smaller value returns the correct value.  If "fac[n]"
has the correct value of "fac[n-1]", then we notice that we need only
multiply "fac[n-1]" by "n", and our definition of "fac[n]" will be correct.
We thus define the factorial function to invoke itself with a parameter
value which is simpler, namely one less than the original value, and then
to take the result of that function call and multiply its value by "n".
Hence the definition is "fac[n]:=n fac[n-1]".

Examples:  Zero Tolerance

No preceding zeros

Suppose we want to eliminate all zeros at the beginning of a list.  We seek
a function, therefore, which takes a list and returns a list with the zeros
at the beginning removed.  The parameter values of the function are then
lists, and a good place to begin for a notion of "simpler" parameters is to
examine the length of the list.  The base case, the simplest case for which
our function must perform the operation, is an empty list (a list with no
elements), and in that case there is nothing to do but return the list,
since it had no zeros to eliminate.  Let's go ahead and define our function
for this base case.

Clear[elimZero]
elimZero[{}] := {}

Now we assume that our function will work on any "small" list; we need only
decide what it should do with a "larger" list:  what piece of the
programming task it should perform, and how it should invoke the function
again with a simpler list.  We may reason as follows:  if a list has a
beginning zero, we should drop it and invoke our function again with this
new list; otherwise we will just return the list itself.  Note that we are
applying the first type of recursion stated above, in which the function
performs an operation first and then invokes the function again.  We
implement our procedure as follows:

elimZero[L_List] :=
                        If[First[L]==0,elimZero[Rest[L]],L]

Thus our function takes a list and examines the first element.  If the
first element is a zero, then it "drops" it---by taking only the remainder
of the list---and applies the function again to this resulting list,
returning the result of this invocation.  Otherwise, the function simply
returns the entire list.  Note that we are making explicit use of the
functions "First[ ]", which returns the first element of a list, and "Rest[
]", which returns the list without its first element.

elimZero[{0,0,0,4,5}]

No ultimate zeros

How would we rewrite "elimZero[ ]" to perform similarly, removing zeros not
from the beginning but from the end of the list?  We would simply have the
function consider the last element of the list instead of the first,
calling the function again if the last element was a zero.  We can use the
function "Last[ ]" to extract the last element of the list, but we will
need to use "Drop[  ,-1]" to extract all of the elements of the list save
the last.

Clear[elimZeroAtEnd]
elimZeroAtEnd[{}] := {}
elimZeroAtEnd[L_List] :=
                        If[Last[L]==0,elimZeroAtEnd[Drop[L,-1]],L]

elimZeroAtEnd[{4,5,0,0,0}]

No zeros at all

Suppose now that we want to rid a list of all zeros.  How could we do this
recursively?  (We could surely use "Select[list,(#!=0)&]", but that's not
recursive.)  Here we must step back.  The base case is the same---a
parameter value of "{}", and a return value of "{}"---but we must consider
what small operation our recursive function must accomplish, and how we
will simplify the value of the parameter.  One way to start is to surmise
that the function should consider one element of the list at a time.  If
zero, our function should not return it; if not, our function should return
it.  But this line of thought is not yet recursive, since we do not want
our function to consider each element of the list, one at a time; instead,
we want our function to perform one operation, say by deciding what to do
with one element of the list, and then to invoke itself again, say with the
rest of the list.  We think thus in terms of entire lists where we envision
our function's examining only the first element.  This better line of
thought proceeds as follows:  if the first element is a zero, we  take the
element off and apply our function again to the new list; if the first
element is not a zero, we still apply our function to the rest of the list
but then take the resulting list and put the first element back on.  Note
that we are certainly allowed to manipulate the result of a call to a
recursive function!  Let's take a look.

Clear[killZero]
killZero[{}] := {}
killZero[L_List] :=
   If[First[L]==0,killZero[Rest[L]],
   Prepend[killZero[Rest[L]],First[L]]]

If the first element of the list is a zero, we return the result of
applying our function again to the remainder of the list.  If the first
element of the list is not zero, we must alter the result of applying our
function to the remainder of the list, by placing the first element back
on.

killZero[{3,4,0,5,6,0,7,7,0,7,0}]

Counting the zeros

Now let's consider how we might recursively count all of the zeros in a
list.  (Again, "Count[list,0]" simply answers the question, but, who knows,
maybe "Count[ ]" has a recursive definition!)  Thinking recursively, we see
that we want our function to consider one element of a list and then pass
the rest of the list on to the function again.  What changes now is that
instead of returning lists, we will be returning numbers, namely, the
number of zeros found in the list.  We can define the function recursively,
then, by checking to see if the first element of the list is a zero, and,
if so, adding 1 to the result of applying the function to the rest of the
list, and if not, adding 0 to the result of applying the function to the
rest of the list.

Clear[countZeros]
countZeros[{}] := 0
countZeros[L_List] :=
  If[First[L]==0,1+countZeros[Rest[L]],
                        countZeros[Rest[L]]
  ]

countZeros[{4,5,0,0,3,4}]

Notice that the return value of the definition of "countZeros[ ]" is an
Integer, and that the base case returns a 0.

What Recursion is Not

We have considered several examples of recursion, and it will be useful to
know what sorts of code will not qualify, although they do return the
correct answers.  First, use of a repetition function ("Map[ ]",
"MapThread[ ]", "Nest[ ]", "NestList[ ]", "Fold[ ]", "FoldList[ ]", "Table[
]", "Apply[ ]", and so on, being our "adverbs") will generally disqualify a
method as purely recursive, for the repetition is accomplished externally
from the nested function calls.  Also, repetition accomplished with a loop
structure, such as a "While[ ]", a "Do[ ]", or some other repetition
command, is explicitly forbidden.  Here are some examples of non-recursive
solutions to the problems above.

No preceding zeros

Clear[elimZero]
elimZero[l_List] := Module[{testAndAppend},
                        testAndAppend[l1_List, l2_] :=                  
                           If[l2==0,l1,Append[l1,l2]];
                        Fold[testAndAppend,{},l]
                        ]

elimZero[{0,0,0,4,5}]

Here we're explicitly using "Fold[ ]" to accomplish the repetition.

No ultimate zeros

Clear[elimZeroAtEnd]
elimZeroAtEnd[l_List] := Module[{c,d},
                        c=Length[l]; d=0;
                        While[c>=1,
                                         If[l[[c]]==0,d++]
                                         c--
                        ];
                        Drop[l,-d]
                        ]

elimZeroAtEnd[{4,5,0,0,0}]

Here we are using a special repetition construct, the "While" construct, to
count the number of zeros at the end, and then dropping them all at once.

No zeros at all

Clear[killZero]
killZero[l_List] :=
   l[[
      Flatten[
         Position[l,_?((#!=0)&)]
      ]
    ]]

killZero[{3,4,0,5,6,0,7,7,0,7,0}]

Here we are running through the list ahead of time to find the nonzero
entries and then choosing them out of the list.

Counting the zeros

Clear[countZeros]
countZeros[l_List] :=
   Apply[Plus,
                        Table[ If[l[[i]]==0,1,0] ,{i,1,Length[l]} ]
   ]

countZeros[{4,5,0,0,3,4}]

Here we are making "Table[ ]" do our work for us.