16. Recursion I:  Passing the Buck

Last revision:  February 8 1999

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.

Mathematica operations/structures introduced: 
     recursive definitions
     First[]
     Rest[]
     Last[]
     While[]

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 suspended, 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 suspended, 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.