Many programmers have an unfortunate fear of recursion. The fear is unfortunate because recursion makes certain kinds of programming so easy.
Seymour Papert, who is responsible for the teaching of the recursive programming language Logo to grade school children, has reported that children readily learn the concept. So why do so many programmers have difficulty with it? I think there are two reasons: It has been explained poorly and they learned iteration first.
It is said that if you give a man a hammer, he'll see the world as a nail. Likewise, if you give a programmer iteration, she'll see problems as essentially iterative in nature. But -- some of them aren't.
If you are already comfortable with recursion, this tip may have little to offer. If not, this tip has the potential to save you a lot of time. For most of you, the potential won't be realized very often, but when it is, the effort of adding recursion to the way you look at programming will be worth it.
Both iteration and recursion are about repeating actions and repeating actions is natural for all people. How many times have you heard "just keep doing that until ..."?
With iteration, you can imagine your self doing the same thing over and over. The world around you changes as you do it, but your actions and choices are the same.
With recursion, you can imagine cloning yourself to repeat an action. Your clone's actions and choices are the same as yours. When it is time to repeat again, your clone will may make another clone, and so on. The world around you may change in a way that you and your clones can all recognize, but each clone has experiences that are not shared with others.
The actions and choices which you and your clones repeat are described in a procedure (which may, or may not, return a value). The experiences that are unique to each one of you are in the procedure's local variables. (That includes parameters that are passed by value.)
The shared environment can be in variables that are regional to the procedure or are in parameters that are passed by reference. Often, these variables have to be initialized before the recursive action can begin. For that reason, recursive procedures are often not invoked directly. Instead, they are invoked through a recursion initializer, i.e. a "wrapper" procedure that the outside world uses to interface with the recursive procedure.
Keeping an army of clones coordinated on one task may seem a daunting enterprise, but recursion is not parallel processing -- only one clone is active at any one time. You, and some other clones, may be waiting to be reactivated, but the pattern of inactive clones always looks like this:
you (since you are the first clone we'll call you clone 1) a clone you activated -- call it clone 2 a clone activated by clone 2 -- call it clone 3 ... a clone activated by clone k-1 -- call it clone k
It is clone k+1 (activated by clone k) who is active and currently at work. The rest of you are waiting for a report from the clone you activated.
This pattern fits not only the rather simple examples shown in this tip but also more complicated uses of recursion where you might activate two or more clones while doing your thing. In all such cases, only one clone is active at a time -- you will not activate an additional clone until the first has finished and reported back.
The report from your clone may, or may not, say anything and when you get it you may, or may not, have some more work to do. In the simplest case, the report says nothing and you are finished when your clone reports back. As shown in the next example, this is the case that is like iteration. A Simple Example
Here's an example of the simplest form of recursion. This recursive procedure inputs a number, adds it to an environment variable and starts a clone to repeat the process. That clone which is asked to input a number beyond the end of the input file simply does nothing.
procedure recursAdd
inputa number X
if input was successful then
Sum := Sum + X recursAdd
endif
Because the variable Sum must be initialized, a recursion initializer is required. This procedure looks to the outside world like a procedure which adds up a series of numbers found in an input file. It accomplishes this by initializing Sum and invoking recursAdd to do the real work:
procedure inputSum Sum := 0 open input file recursAdd return Sum
One nice thing about the Pascal-influenced languages is that the procedure recursAdd can be nested within the procedure inputSum so that the variable Sum becomes part of the environment that all clones share. To get the same effect in the C-like languages, declare recursAdd this way:
void recursAdd(int * Sum);
so that all clones can refer to the same Sum. Or, declare Sum to be static in a file that contains only recursAdd and inputSum.
We'll look at a different recursive solution to the same problem below. Now, let's compare this solution with an iterative one. To make the similarities more apparent, we'll put the loop in inputSum and keep recursAdd much the same -- although it won't be recursive anymore.
Here is a nonrecursive version of recursAdd that is very similar to the recursive one. The main difference is that instead of deciding to start a clone, the procedure sets a boolean variable DoAgain.
procedure recursAdd
input a number X
if input was successful then
Sum := Sum + X
DoAgain := true
else
DoAgain := false
endif
Here's the procedure that does the adding.
procedure inputSum
Sum := 0
open input file
repeat
recursAdd
until not DoAgain
return Sum
To see the iterative version without the extra procedure simply substitute its code:
procedure inputSum
Sum := 0
open input file
repeat
input a number X
if input was successful then
Sum := Sum + X
DoAgain := true
else
DoAgain := false
endif
until not DoAgain
return Sum
This can be cleaned up a little but, as shown, it suffices to
show the strong similarity between simple recursion and iteration. A Variation
The previous example was chosen to show the similarity between recursion and iteration. The additional power of recursion arises from your ability to start a clone in the middle of a task and then complete the task when the clone is finished.
In the previous example, the addition is done before the clone is started. That means Sum grows with each new number as it is read. When adding up a sequence of numbers, recursion gives you the power to do the addition after your clone has found the sum of all subsequent numbers. That means that you will save the number you have read until Sum is the sum of all subsequent numbers. Only then will you increment Sum by you input number.
However, since you are going to add your number to the sum of subsequent numbers and since your clone has the sum of subsequent numbers to return to you, it is possible to dispense with the variable Sum. Instead, of incrementing Sum, you and your clones simply return the total that you are responsible for -- basing this total on the subtotal provided by a clone. Here's is this new (recursive) version of recursAdd.
procedure recursAdd
input a number X
if input was successful then
return X + recursAdd
else
return 0
endif
Any clone that follows this plan will return the sum of all numbers that were read after it read its own number. The recursion initializer also becomes simpler:
procedure inputSum open input file return recursAdd
Indeed, if the input is to come from standard input, there is no
need to have the recursion initializer at all.
A Real Example
I claimed at the beginning that some problems are easier to solve with recursion than iteration. Many of these problems involve recursive data structures. An example of that stamp would be difficult to motivate because I would have to explain why the recursive data structure made something else easier. Here is an example that will require less motivtion.
The problem is to write an integer on the standard output file. The only catch is that you are limited to the most primitive form of output, i.e. byte-by-byte output but the integer is in the form used by your computer for integer arithmetic -- definitely not a digit by digit form.
Of course, this problem has you implementing something that has already been done for you with most programming languages. Why do it if it has been done? Only to see that doing it is easier with recursion than without.
The tools you have for solving this problem are
procedure divide(Dividend,Divisor,Quotent,Remainder)
which divides the integer Divisor into the integer Dividend producing the integer Quotient and the remainder Remainder. All numbers must be positive. You certainly know how to implement divide in your favorite programming language. You may also know it can usually be done in one step in assembly languages.
You also know that divide can be used to peel digits off the right of positive integers. For example, to peel the digits off of 39, do these steps
divide(39,10,SingleRemainingDigit,RightMostDigit) divide(SingleRemainingDigit,10,Zero,LeftMostDigit)
After these two statements have executed, the indicated variables have these values:
SingleRemainingDigit = 3, RightMostDigit = 9 Zero = 0, LeftMostDigit = 3
Of course, most of these variables have names that would not make sense in the general case. The exception is RightMostDigit which makes sense after any division by 10.
What makes this problem recursive is that the first step you can take is to obtain the rightmost digit but the first thing you must do is write the leftmost digit. You solve this problem by peeling off the rightmost digit, telling your clone to write the number that is left, and, when your clone is done, writing the digit you peeled off.
This plan works for positive integers. The problem of negative integers can be solved in the recursion initializer. Here is an implementation:
procedure writePosInt(I)
divide(I,10,PeeledI,PeeledDigit)
if PeeledI != 0 then
writePosInt(PeeledI)
endif
writeChar(digitToChar(PeeledDigit))
Before writing the recursion initializing procedure, it is necessary to notice that both negative integers and 0 have yet to be handled correctly and that neither case is difficult with the tools now in hand.
procedure writeInt( I )
if I<0 then
writeChar('-')
writePosInt(-I)
elsif I==0 then
writeChar(digitToChar(0))
else
writePosInt(I)
endif
If you think this problem is easier to solve iteratively, you are welcome to try. Remember you have to limit yourself to primitive steps or it is not a real test.
Copyright 1996, J A Zimmer
These programming tips are distributed to individuals by the copyright holder, J Adrian Zimmer. All other distribution (including but not limited to internal distribution within an organization and mirroring of any kind) is forbidden without written consent of the copyright holder. The meaning of the word "distribution" here includes any kind of copying for use by a different person or organization than the one who obtained the programming tip from copyright holder.