To recurse or not to recurse. (repeating a function in programming) Edward Grundler.
To Recurse Or Not To Recurse
Some programming languages, e.g. Pascal, allow recursion. Recursion is a very powerful technique that it usually misunderstood, if it is understood at all. To compound the problem, recursion is usually taught with bad examples. The purpose of this article is to improve your understanding of recursion and demonstrate its power.
Before we get too far, maybe we should settle on what recursion is. Recursion means to repeat. To use recursion in a program means to enter repeatedly a function or procedure from within the scope of that function or procedure. This brings us to one of the bad examples of recursion.
Consider the program in Listing 1. This and all programs in this article are written in standard Pascal. The function named SUM is a recursive function. Let's examine how it works.
Suppose you enter a 3 for the first value of N. This 3 is passed to the variable I in function SUM. Since I is not equal to 1, the else statement tries to compute SUM: = I + SUM (3-1). Now here is the recursive call to SUM. Function SUM must be called to evaluate SUM(2). On this entry to (a new activation of) SUM, I is 2.
Again, since I is not equal to 1, the else statement tries to compute SUM :=I + SUM(2-1). To evaluate SUM(1), a new activation of function SUM is generated and I is assigned the value of 1. Since I is now 1, the value 1 is assigned to SUM. This value is passed to the calling statement and the third activation of function SUM is discarded.
The second activation of SUM can now add 2 to 1 to complete its job. The value 3 is passed to the calling statement, and the second activation of SUM is discarded.
At this point, the first activation of SUM adds 3 to the 3 that was passed to it from the second activation of SUM and passes 6 to the calling statement in the main program. The first activation of SUM is discarded. The main program then writes 6 to the output file and returns to get a new number.
This is a perfectly legal way to find the sum of the first N integers. It is not a very practical or efficient way, however. The program in Listing 2 is a much better way to accomplish the same thing. This solution was included to show that, in general, a problem that can be solved with recursion, can also be solved with simple iteration. Of course, this is also a bed way to solve this particular problem. The program in Listing 3 is the best solution for obtaining the sum of the first N integers.
Another bad example of recursion that frequently shows up in programming classes is finding N! (N factorial) by recursion. N! is defined to be 1 if N is 0. If N is not 3, then N! = N(N-1)!. Notice that the definition itself is recursive. The program in Listing 4 is the recursive solution. Note the similarity between the programs in Listing 1 and 4.
This is not the best way to handle the factorial problem either. If only a few factorials need to be calculated, the best approach is the method in Listing 2. If many factorials must be calculated during the course of a program, the program in Listing 5 offers the best way. MAX is set to 7 in this example because 8! is beyond the range of most home computers. 8! = 40320. If you have a really big computer, MAX can be made 16 or 17 before the limits of the computer's integer are reached. The point here is that it is much more efficient to compute the small number of values once and keep them in a look-up table.
At this point you might be asking if recursion serves any purpose at all. The answer to this question is an emphatic yes. The program in Listing 6 uses two recursive procedures that greatly simplify the algorithms that they implement. The program is a sorting routine that sorts integers. In general, any type of data could be stored in the records and any field in the record, other than the pointers, could be used as the sort field.
The program in Listing 6 uses insertion sort to accomplish the sort. In other words, the new data are entered into the list at the proper point as they are entered. This is probably the most natural method of sorting that exists. The main problem with an insertion sort is that if the list is an array or some similar data structure, the list must be opened to do the insertion. To open the list, everything from the point of insertion to the end of the list must be moved.
The program in Listing 6 avoids this problem by using a binary tree as the data structure. With a binary tree, nothing needs to be moved. One only needs to find the proper point in the tree and adjust the necessary pointers.
In program #6, which sorts 20 numbers in a FOR-DO loop, the main program generates a new record and then reads the next number from the input file into the record for that integer (INT) field. Both the left and right pointers are set to NIL and, finally, the record is placed in the tree.
Prior to the first number being entered, the tree appears as in Figure 1. With no data in the tree, its base pointer is set to NIL.
Now let's suppose that the first number entered is a 32. The main program generates a record and calls procedure PLACE, which enters it as the base record. After this occurs, the tree appears as in Figure 2.
With this accomplished, the loop is repeated to get the second number. Suppose it is 52. Again, a record is created and its pointers are set to NIL. This time when procedure PLACE is called, the base record has already been assigned. Instead, PLACE compares 52 with 32 and makes a recursive call to procedure PLACE, pointing to the right subtree of the record containing the 32. If we then enter a 30, the new record is placed in the left subtree of the record containing 32. Our tree now looks like Figure 3.
For the fourth number, let's enter 54. The main program generates a new record and calls procedure PLACE as before. PLACE sees that 54 is larger than 32 and makes a recursive call to procedure PLACE using the right subtree of record 32 as the tree in which to place the new record containing 54.
On this call, PLACE compares 54 with 52 and makes a second recursive call to procedure PLACE using the right subtree pointer of the record containing 52. This leaves the tree as shown in Figure 4.
If we continue our entries as follows: 65, 64, 16, 47, 32, 56, 32, 38, 66, 55, 33, 88, 43, 26, 45, 63; we end up with the tree shown in Figure 5. Notice that six levels of recursion are required to place 55 and 63 in the tree.
Since the tree now contains 20 items, the FOR-DO loop is complete, and the main program makes a single call to procedure TRAVERSE to print the entire list.
Procedure TRAVERSE executes an in-order traverse of the tree and is deceptively simple. As can be seen, the body contains only three statements, two of which are recursive calls to TRAVERSE. The first statement is a recursive call to traverse the left subtree of the current record. The second statement writes the data in the current record. The third statement is a recursive call to traverse the right subtree of the current node.
Following the action of procedure TRAVERSE, we enter looking at the record containing 32 under the base. An immediate call is made to TRAVERSE looking at the record containing 30. Another call is made to TRAVERSE, but this time we are looking at the record containing 16. Since this record has no left subtree, the 16 is sent to the output file and a call to TRAVERSE is made looking at the record containing 26. Since the left subtree of this record is empty, no call to TRAVERSE is made, and the 26 is sent to the output file. Since the right subtree of this record is also empty, a return is made to the call at the record containing 16. We have now completed all action on this record and a return is made to the record containing 30. We can now print the 30 and traverse its right subtree.
This action continues until the final item has been printed. The output is printed in the following order: 16, 26, 30, 32, 32, 32, 33, 38, 43, 45, 47, 52, 54, 55, 56, 63, 64, 65, 66, 88.
For the doubters of the power of recursion in this situation: Try writing a program to place records in a binary tree. Do an in-order traverse of the tree without recursion and compare with the single statement in procedure PLACE and the three statements in procedure TRAVERSE.
In summary, if you use a recursive language like Pascal, it would be beneficial to learn how and when to use recursion. After you learn to do sums and factorials in a recursive manner, forget them and concentrate on the beneficial uses of recursion that save time and energy (yours).
Table: Listing 1.
Table: Listing 2.
Table: Listing 3.
Table: Listing 4.
Table: Listing 5.
Table: Listing 6.
Photo: Figure 1.
Photo: Figure 2.
Photo: Figure 3.
Photo: Figure 4.
Photo: Figure 5.