# CHAPTER 4: INTRODUCTION TO RECURSION, STACKS, AND QUEUES

Presents recursion as a special case of the top-down approach to problem solving

Explains recursive programs

how to understand them

how to simulate them

how to write them

Shows how recursive programs may be translated by a compiler or written in a non-recursive language

Introduces two more data structures

the stack

the queue

Illustrates the use of a stack with operations

setstack

empty

push

pop

Case study--checking sequences for proper nesting

uses the stack and treats it as a data abstraction

# 4.1: What Is Recursion?

Self-reference is not without its pitfalls. You have most likely encountered the frustration of circular definitions in the dictionary, such as "Fashion pertains to style" and "Style pertains to fashion." From this you conclude that "Fashion pertains to fashion." This kind of self-reference conveys no information; it is to be avoided. "This sentence is false" is another type of self-reference to be avoided, for it tells us nothing. If true it must be false, and if false it must be true. Nevertheless, self-reference is an important technique in finding and expressing solutions to problems.

Recall that the top-down approach to problem solving entails breaking down an initial problem into smaller component problems. These components need not be related except in the sense that putting their solutions together yields a solution to the original problem. If any of these component problems is identical in structure to the initial problem, the solution is said to be recursive and the problem is said to be solved by recursion. If the solution and its components are functionally modularized, then the solution will refer to itself. Recursion is thus a special case of the top-down design methodology.

Suppose a traveler asks you, "How do I get there from here?" You might respond with a complete set of directions, but if the directions are too complex, or you are not sure, your response might be: "Go to the main street, turn left, continue for one mile, and then ask, "How do I get there from here?" This is an example of recursion. The traveler wanted directions to a destination. In solving the problem, you provided an initial small step leading toward the traveler's goal. After taking that step, the traveler will be confronted with a new version of the original problem. This new problem, while identical in form to the original, involves a new starting location closer to the destination.

Cursing is often used to belittle a problem; recursing has the same effect! Recursion, when appropriate, can give relatively easy-to-understand and concise descriptions for complex tasks. Still, care must be taken in its use, or else efficiency of storage and execution time will be sacrificed.

# 4.2: Using Recursion

Applying the recursive method is just like applying the top-down approach, but it can be tricky; it presents conceptual difficulties for many students. The purpose of this section is to show how to develop and understand recursive solutions. Some illustrative examples are provided to help you get the idea. Practice will help you become skilled in the use of recursion.

## 4.2.1 The Towers of Hanoi

Consider the case when n = 4, shown in Figure 4.1(a). The following sequence of instructions provides a solution.

1. Move the top disk from peg l to peg 2.

2. Move the top disk from peg 1 to peg 3.

3. Move the top disk from peg 2 to peg 3.

4. Move the top disk from peg 1 to peg 2.

5. Move the top disk from peg 3 to peg 1.

6. Move the top disk from peg 3 to peg 2.

7. Move the top disk from peg 1 to peg 2.

8. Move the top disk from peg 1 to peg 3.

9. Move the top disk from peg 2 to peg 3.

10. Move the top disk from peg 2 to peg 1.

11. Move the top disk from peg 3 to peg 1.

12. Move the top disk from peg 2 to peg 3.

13. Move the top disk from peg 1 to peg 2.

14. Move the top disk from peg 1 to peg 3.

15. Move the top disk from peg 2 to peg 3.

#### Figure 4.1 The Towers of Hanoi Problem

It is not difficult to arrive at such a solution for a specific small value of n. Try to find a solution for n = 5. You will find that, even though you succeed after some trial and error, creating a solution for n = 25 is indeed a formidable task. You may even be too old to care by the time you finish. If a particular value of n gives so much trouble, how does one specify a solution for any n, when one does not even know what value n will have?

One answer is to apply the technique of recursion. This means attempting to break down the problem into component problems that can be solved directly or that are identical to the original problem but involve a smaller number of disks. The three component problems below fit the requirements of this framework.

1. Move the top n - 1 disks from peg 1 to peg 2.

2. Move the top disk from peg 1 to peg 3.

3. Move the top n - 1 disks from peg 2 to peg 3.

If these three problems can be solved, and their solutions are applied in sequence to the initial situation, then the result is a solution to the original problem. This can be seen from parts (a)-(d) of Figure 4.1, which show the consecutive situations after each is applied.

We now generalize the original problem:

Move the top n disks from peg i to peg f.

i denotes the initial peg on which the top n disks to be relocated reside, and f denotes the final peg to which they are to be relocated. Let a denote the third available peg. Solving the original problem, which has only n disks, is equivalent to solving the generalized problem with i taken as 1 and f taken as 3. This is because the moves that accomplish its solution will also work for the generalized problem, since any disks below the top n are larger than they are, so their existence doesn't render any of the moves illegal. Solving the first component problem is equivalent to solving the generalized problem with n replaced by n - 1, i by 1, and â by 2. It is now apparent that the original problem, and the components 1, 2, and 3, have structure identical to the generalized problem, but the components involve fewer disks. They also involve different initial, available, and final pegs. This is why it was necessary to generalize the original problem.

Suppose you have found a solution to the generalization and denote it by towers(n,i,a,f). Then, as just shown, the application of the solutions to components 1, 2, and 3, in sequence, will be a solution to the original problem. A recursive definition for towers(n,i,a,f) can now be expressed as follows. Note that moves in towers(n,i,a,f) are from peg i to peg f--that is, from the second parameter to the fourth parameter. The first parameter specifies the number of top disks, on the peg given by the second parameter, that are to be moved.

`To obtain towers(n,i,a,f):`

`If n = 1, then`

`move the top disk from peg i to peg f`

`else`

`apply towers(n - 1,i,f,a)`

`moves the top disks from peg i to peg f`

`apply towers(n - 1,a,i,f).`

This is the recursive algorithm for the Towers of Hanoi problem. Notice that the definition gives an explicit solution for the special case when n = l and an implicit solution for the case of n > 1.

To use the method of recursion we must recognize when it is applicable and find a correct way to generalize the original problem and then to break down the generalization. We have been successful and have found a recursive algorithm. Because no further refinement is needed, the corresponding recursive program can be written directly using functional modularization:

`towers(n,i,a,f)`

`/* Moves the top n disks from peg i to peg f`

`*/`

`int n,i,a,f;`

`{`

`if(n == 1)`

`printf("\n %d -> %d\n",i,f);`

`else`

`{`

`towers(n-1,i,f,a);`

[1]

`printf("\n %d -> %d\n",i,f);`

`towers(n-1,a,i,f);`

[2]

`}`

`}`

The labels [1] and [2] are not part of the program but are used later as references when explaining the program. It is essential to see that this function has been written just like any other; whenever a component task is available as a function, we invoke it to carry out that task. The feature that distinguishes it and makes it a recursive function is that the required functions happen to be the function itself. The references within towers to itself are allowed in recursive languages.

## 4.2.2 Verifying and Simulating a Recursive Program

For the case when n exceeds l, Figure 4.1 has already confirmed that as long as the three component functions work properly, then towers(n,i,a,f) will also. Note that these components correspond to smaller values of n. Mathematically inclined readers may recognize that this really amounts to a proof of correctness for towers using mathematical induction on n. One of the advantages of recursive programs is that they may be proven correct more easily in this way.

In order to understand how a recursive program actually executes, it is necessary to simulate its execution. Below are the first few steps of the simulation for a call to towers(n,i,a,f) with the values 4, 1, 2, 3 -- that is, towers(4,1,2,3). It will soon become apparent that considerable bookkeeping is involved, requiring an organized way to do it.

Since n is greater than 1, the procedure requires the sequential execution of

`towers(3,1,3,2)`

`printf("\n %d -> %d\n",1,3);`

and

`towers(3,2,1,3)`

To do this requires suspending the execution of towers(4,1,2,3) at this point in order to simulate the first recursive call, towers(3,1,3,2). Note that after this recursive call is completed, 13 is to be output. (1 3 means "Move the top disk from peg 1 to peg 3.") Then another recursive call must be simulated, towers(3,2,1,3).

Dealing with towers(3,1,3,2), since n > 1, the commands

`towers(2,1,2,3)`

`printf("\n %d -> %d\n",1,2);`

and

`towers(2,3,1,2)`

must be carried out sequentially. Now the execution of towers(3,1,3,2) must be suspended in order to simulate the second recursive call, towers(2,1,2,3). Note that after this recursive call is completed, 1 2 is to be output, and then another recursive call must be simulated: towers(2,3,1,2).

Dealing with towers(2,1,2,3), since n > 1,

`towers(1,1,3,2)`

`printf("\n %d -> %d\n",1,3);`

and

`towers(1,2,1,3)`

must be carried out sequentially. These two calls to towers represent the third and fourth recursive calls. They both complete without generating any new recursive calls. The three statements result in the outputting of l 2, 1 3, and 2 3, respectively. This completes the second recursive call (towers(2,1,2,3)) so we must pick up the simulation at the proper point, which is to output l 2 and then make the fifth recursive call to simulate towers(2,3,1,2).

#### Figure 4.2 Bookkeeping for the Simulation of a Recursive Program

Enough is enough! At this point you may feel like a juggler with too few hands and too many recursive calls. Figure 4.2 represents a convenient way to keep track of the complete simulation; it may be generated as the simulation proceeds. The figure traces the recursive calls made to towers as the initial call to towers(4,1,2,3) is executed to completion. Each recursive call is numbered to show whether it is the first, second, . . . , or fourteenth. The bracketed return values indicate the labeled statement of procedure towers at which the preceding recursive call is to resume when the next call is completed. For example, when towers(3,1,3,2) is completed, towers(4,1,2,3) resumes at [l]. Our simulation stopped just as the fifth recursive call was to be carried out. The figure uses shorthand for the output. For example, l 2 means, "move the top disk from peg l to peg 2." The solution is the same as our earlier one.

Figure 4.2 indicates very clearly what information must be available at each point in the simulation (or execution of the program) in order to carry it out. Specifically, it is necessary to know the following information:

The four parameter values of the call currently being carried out

Where to resume when the call currently being carried out is completed

For example, when the third recursive call is completed, resumption must be at the printf statement of the second recursive call; when the fifth recursive call is completed, resumption must be at the end of the first recursive call; and finally, after the initial recursive call is completed, resumption must be at the proper point in the program that called towers originally.

Notice that the last three parameters are never modified by towers, but the first parameter, which corresponds to the number of disks for the current problem, is modified. For instance, the first recursive call to towers(3,1,3,2) has modified the first parameter, making it 3 rather than 4 as it was initially. It is important that this modification be kept local to towers(3,1,3,2), not reflected back to towers(4,1,2,3), the initial call.

`To obtain towers(n,i,a,f):`

`If n = 1, then`

`move the top disk from i to f`

`else`

`apply towers (n - 1,i,f,a)`

`move the top disk from i to f`

`apply towers(n - 1,a,i,f).`

l. Label the disks l, 2, . . . , n in increasing order of size.

2. Label the pegs i, a, and f, n + 1, n + 2, and n + 3, respectively.

3. Move the smallest disk onto another disk with an even label or onto an empty peg with an even label.

4. While all disks are not on the same peg

a. move the second smallest top disk onto the peg not containing the smallest disk

b. move the smallest disk onto another disk with an even label or onto an empty peg with an even label.

The Tower of Babel failed for lack of communication. The construction workers did not speak the same language. While recursion allows the solution to the Towers of Hanoi to be specified conveniently, it is execution time that causes trouble. The diagram of Figure 4.1 shows that the construction of the new tower of disks will take 24 - 1 or fifteen moves. It is not difficult to generalize the diagram to n disks to conclude that 2n - 1 moves will be needed for n disks (see Exercise 7). Even with Olympic-caliber construction workers, it would take over one thousand years to complete the tower for 50 disks.

## 4.2.3 The Length of a List

1. Determine the length of a list

2. Create a list that is a copy of another list

3. Count checkerboard placements

4. Generate all permutations of n integers and process each one. (This is applied to the stable marriage problem.)

In addition to providing repetition so that you can become more familiar with and understand recursion better, the examples provide a background to show how local and global variables and parameters are treated in recursive programs and why recursive solutions are not always the best. A list may be thought of as being either a null list or as one record followed by another list (the link field of the record plays the role of the head of this other list). This is nothing but a way to define a list recursively. Consider the recursive function defined by

`length(listname)`

`/* Returns the number of records`

`in the list pointed to by listname.`

`*/`

`listpointer listname;`

`{`

`listpointer setnull(),next();`

`if(listname == setnull())`

`return(0);`

`else`

`return(1 + length(next(listname)));`

`}`

This function returns the length of the list, listname. To verify that this is correct we must check

1. The null list. It returns with length = 0.

2. A one-record list followed by another list. It returns length = 1 + the length of the list after the first record.

It is correct, since its value is correct for each case. Of course it is correct--after all, the length of a null list is zero, and the length of a list with at least one record is 1 for the record, plus the length of the rest of the list beyond the first record ! This was how length was written in the first place.

## 4.2.4 Copying a List

`copy(first,psecond)`

`/* Creates a new list which is a copy`

`of the list pointed to by first and`

`whose head is second`

`*/`

`listpointer first,*psecond;`

`{`

`listpointer null, rest,setnull(),avail(),next();`

`null = setnull();`

`if(first == null)`

`*psecond = null;`

`else`

`{`

`*psecond = avail();`

`setinfo(*psecond,first);`

`copy(next(first),&rest);`

`setlink(*psecond,rest);`

`}`

`}`

When first is the null list, copy faithfully terminates with the copy also a null list. When first is a one-record list, copy sets second to point to storage allocated for a record and sets the information field value of this record to the value of the information field in first's first record. The recursive call to copy(next(first),&rest) is then an invocation of copy to copy the null list, since next(first) is null in this case. Assuming it performs its task correctly, rest will be null when it returns. The link field of the record pointed to by second is then set to the value of rest (the null pointer), and the initial call to copy terminates correctly.

Similarly, had there been more than one record in first's list, the recursive call to copy would have returned with rest pointing to a correct copy of the list pointed to by next(first). Setlink would correctly place a pointer to that correct copy into the link field of the record pointed to by second, and the initial call would terminate correctly. This verifies that copy is correct in all cases. Again, to copy the null list is easy. To copy a list with at least one record, simply copy that record, copy the rest of the list beyond the first record, and append that copy to the copy of the first record. This is how copy was written!

If you are confronted with a recursive program and want to understand it, approach it in the same way as you would a nonrecursive program. Assume that any functions that are called perform their functions correctly, and then attempt to see what the program itself does. Sometimes this will be apparent, as it was for towers and copy, and sometimes a simulation of the program helps to increase comprehension. Imagine, for example, that you were not told what copy did. It wouldn't have been so easy to find out without simulating some simple cases.

## 4.2.5 Local and Global Variables and Parameters

This situation holds for recursion also. Each recursive call to a function produces its own copies of automatic local variables. Thus there may be many different values for the same local variable--each applicable to its own invocation of the function. As with nonrecursion, there is only one storage allocation for a global or a static variable, and it holds the last value of the variable.

The only way to change the original value of a variable used as a parameter is to pass the address of the parameter instead of its value. This is done automatically in the case of arrays and character strings. When an array is passed as a parameter, the address of the first storage location in the array is passed. This negates the need to make local copies of all the values of the array in the function and thus waste memory. Addresses for parameters can also be passed as pointers A copy is made in the function and is local to the function. Using the pointer, the value of the parameter can be changed.

`simple (x,py)`

`int x, *py;`

`{`

`x = 1;`

`*py = 2;`

`*py = x + *py;`

`}`

Suppose that simple is invoked with actual parameters a and b, containing 0 and 1 respectively. It is invoked by the statement, simple (a,&b). Within the function, x initially has a copy of a as its value--0 in this case. y refers to the storage for b--that is, y is a pointer to the storage for b. The first statement of simple causes x to assume the value l, the second statement causes the storage for b to contain 2, and the third statement sets the storage for b to 3. When the calling program continues, a will still be 0, but b will be 3.

Parameters of recursive programs are treated in just this way. Any time cursive call is made within a recursive program, the recursive call acts just like a call to any function. The only difference is that, since a recursive function may generate many recursive calls during its execution, many local copies of its parameters may be produced. References to a parameter by value during the execution of each recursive call will then mean the current local copy of that parameter. Reference to a parameter passed by a pointer to it always means the same actual parameter.

Null and rest are local variables of the initial call to copy and remain local variables in all subsequent recursive calls. Local copies of null and rest are thus made on any call to copy.

First is passed by value and second by pointer.

Whenever copy is executing and generates a recursive call to copy(next(first),&rest), the actual first parameter of copy is the current copy of next(first)--i.e., the copy associated with the currently executing call to copy. Any references to the first parameter during the generated recursive call refer to the new local copy associated with that call.

When first points to the list as shown in Figure 4.3, and copy(first, second) is executed, the sequence of events and memory configurations that will take place appear in Figure 4.4. First0, first1, first2, first3 refer to the local copies of the actual first parameter associated with the initial, first, second, and third recursive calls to copy, respectively. Similarly for the other variables. A question mark indicates an as yet undefined value. Be sure you understand Figure 4.4 and how it represents the execution of copy.

#### Figure 4.4 Simulation of COPY(FIRST,&SECOND)

`listpointer copy(first)`

`/* Returns a pointer to the first record of a new list which is a`

`copy of the list first.`

`*/`

`listpointer first;`

`{`

`listpointer null,second,setnull(),avail(),next();`

`null = setnull();`

`if (first == null)`

`second = null;`

`else`

`{`

`second = avail();`

`setinfo(second,first);`

`setlink(second,copy(next(first)));`

`}`

`return (second);`

`}`

This version differs from the original version in two ways. One, it has only one parameter, the list to be copied, and two, it returns a pointer to the new copy rather than setting a second parameter to point to the new copy.

## 4.2.6 Counting Squares

The third example relates to counting squares. Consider an n X n checkerboard and determine the number of ways a 4 X 4 checkerboard can be placed on it. For example, if n = 5, there are four ways to place a 4 X 4 checkerboard on the 5 X 5 board, as shown below.

For this particular example the solution is easy to see by inspection. However, how do you state an algorithm that produces the result in all cases? This can be done handily using recursion. Suppose you know the number of ways, f(n - 1), in which the 4 X 4 board can be placed on an (n - 1) X (n - 1) board. An additional (n - 3) + (n - 4) placements result from an n X n board, because of the n cells

#### Figure 4.5 An n x n Checkerboard

added at the top and left sides of the (n - 1) X (n - 1) board, as shown in Figure 4.5. There are a total of f(n) = f(n - 1) + (n - 3) + (n - 4) placements for the n X n board, when n 5. If n = 4, f(4) = 1. So the following is true.

`f(n) is`

`1 if n = 4`

`f(n - 1) + (n - 3) + (n - 4) if n  5`

`f(n)`

`int n;`

`{`

`if (n == 4)`

`return (1);`

`else`

`return(f(n-1)+(n-3)+(n-4));`

`}`

If n = 7, the program would execute as follows:

`f(7) = f(6) + (7 - 3) + (7 - 4)`

`f(6) = f(5) + (6 - 3) + (6 - 4)`

`f(5) = f(4) + (5 - 3) + (5 - 4)`

`f(4) = 1`

`f(5) = 1 + 2 + 1 = 4`

`f(6) = 4 + 3 + 2 = 9`

`f(7) = 9 + 4 + 3 = 16`

`f(n)`

`int n;`

`{`

`return((n-3)*(n-3));`

`}`

The recursive solution will take time and storage O(n), whereas the nonrecursive solution requires constant time and storage. Obviously, this solution is better in every way than the recursive solution to this problem. Hence recursion does not always yield the best solution. Just as with any tool, it must be used judiciously. You wouldn't use a bulldozer to dig a two-foot hole in your yard.

## 4.2.7 Permutations

This approach yields a program that traverses the collection of permutations, processing each one and halting when a stable permutation is encountered. Stable may be conveniently invoked to check a permutation for stability. In contrast, the algorithm of Section 2.5 avoids such an exhaustive search by eliminating some permutations from consideration altogether. Still, many problems require just such an exhaustive search and contain a component to produce the permutations. The problem is to write a program to carry out the traversal. The function permutations does this:

`permutations(n)`

`/* Generates and processes each`

`permutation of the integers`

`1 to n.`

`*/`

`int n;`

`{`

`int done;`

`done = FALSE;`

`initialize(n);`

`while (!done)`

`{`

`process(n);`

`next(n,&done);`

`}`

`}`

where next (n,&done) must return, having updated the current permutation to the next permutation, unless the current permutation is the last one, when it simply sets done to true.

The problem is now to refine next. Suppose n = 4 and the first permutation is 3 2 1. Inserting 4 in all possible positions among 1, 2, and 3 gives the first four permutations of 1, 2, 3, and 4.

`4 3 2 1`

`3 4 2 1`

`3 2 4 1`

`3 2 1 4`

Removing 4 leaves 3 2 1. The next four permutations for n = 4 can be obtained by first obtaining the next permutation after 3 2 1 for n = 3. But this next permutation for n = 3 can similarly be obtained by shifting 3 to the right one place, yielding 2 3 1. Then the next four permutations for n = 4 are

`4 2 3 1`

`2 4 3 1`

`2 3 4 1`

`2 3 1 4`

Removing 4 leaves 2 3 1. Again, the next permutation after 2 3 1, 2 1 3, is obtained by shifting 3 right. The next four permutations for n = 4 are

`4 2 1 3`

`2 4 1 3`

`2 1 4 3`

`2 1 3 4`

Continuing this process will produce, in turn,

`4 3 1 2    4 1 3 2           4 1 2 3`

`3 4 1 2    1 4 3 2           1 4 2 3`

`3 1 4 2    1 3 4 2           1 2 4 3`

`3 1 2 4    1 3 2 4    and    1 2 3 4`

`next (n,pdone)`

`If n is not 1, then`

`If n is not at the right end of the current permutation of 1, . . , n then`

`shift it right one position`

`else`

`remove "n" from the current permutation of 1, . . , n`

`next(n - 1,pdone)`

`Insert "n" at the left end of the current permutation of 1, . . , n - 1`

`else`

`set done to true.`

In order to proceed, a data structure to store the permutation must be chosen. To illustrate the effect of this selection, we will use two different structures--arrays and lists. We start by storing the permutation in an array p. Searching for the location of n in p will be avoided by keeping an array l of pointers. Both p and l are defined globally. l[n] points to the location of n in p when next(n,pdone) is invoked. Initialize must set p[i] to n - i + 1 and l[i] to 1 for 1 i n. Next may be defined as

`next(n,pdone)`

`/* Generates the next permutation unless`

`the current one is the last. In this case`

`done is set to true.`

`*/`

`int n,*pdone;`

`{`

`int i;`

`if (n > 1)`

`if (l[n] < n)`

`{`

`p[l[n]] = p[l[n]+1];`

`p[l[n]+1] = n;`

`l[n] = l[n]+1;`

`}`

`else`

`{`

`next(n-1,pdone);`

`for (i=n-1;i>=1;i--)`

`p[i+1] = p[i];`

`p[1] = n;`

`l[n] = 1;`

`}`

`else`

`*pdone = TRUE;`

`}`

Figure 4.6(a) simulates the execution of next(4,pdone) when the current permutation is 2 1 3 4.

`next(n,pdone)`

`/* Generates the next permutation unless`

`the current one is the last. In this case`

`done is set to true.`

`*/`

`int n,*pdone;`

`{`

`if (n > 1)`

`if (ptr[n]->link != NULL)`

`{`

`pred[n]->link = ptr[n]->link;`

`pred[n] = pred[n]->link;`

`ptr[n]->link = pred[n]->link;`

`pred[n]->link = ptr[n];`

`}`

`else`

`{`

`pred[n]->link = NULL;`

`next(n-l,pdone);`

`ptr[n]->link = p->link;`

`p->link = ptr[n];`

`pred[n] = p;`

`}`

`else`

`*pdone = TRUE;`

`}`

Figure 4.6(b) simulates the execution of next(4,pdone) when the current permutation is 2 l 3 4.

#### Figure 4.6 Simulation of NEXT (4,&DONE) When P is 2134

Array Implementation

`#include <stdio.h>`

`#define TRUE 1`

`#define FALSE 0`

`typedef int arraytype[21];`

`arraytype p,l;`

`main()`

`/* Driver for permutations. */`

`{`

`int n;`

`printf("\n n = ?\n");`

`scanf("%d",&n);`

`permutations(n);`

`}`

`permutations(n)`

`/* Generates and processes each`

`permutation of the integers`

`1 to n.`

`*/`

`int n;`

`{`

`int done;`

`done = FALSE;`

`initialize(n);`

`while (!done)`

`{`

`process(n);`

`next(n,&done);`

`}`

`}`

`initialize(n)`

`/* Creates initial permutation */`

`int n;`

`{`

`int i;`

`for (i = 1;i<=n;i++)`

`{`

`p[i] = n - i + 1;`

`l[i] = 1;`

`}`

`}`

`process(n)`

`/* Prints the current permutation */`

`int n;`

`{`

`int i;`

`for (i=1;i<=n;i++)`

`printf("\n%d\n",p[i]);`

`printf("\n");`

`}`

`next(n,pdone)`

`/* Generates the next permutation unless`

`the current one is the last. In this case`

`done is set to true.`

`*/`

`int n,*pdone;`

`{`

`int i;`

`if (n > 1)`

`if (l[n] < n)`

`{`

`p[l[n]] = p[l[n]1];`

`p[l[n]+1] = n;`

`l[n] = l[n]+1;`

`}`

`else`

`{`

`next(n-1,pdone);`

`for (i=n-1;i>=1;i--)`

`p[i+1] = p[i];`

`p[1] = n;`

`l[n] = 1;`

`}`

`else`

`*pdone = TRUE;`

`}`

List Implementation

`#include <stdio.h>`

`#define TRUE l`

`#define FALSE 0`

`#define NULL 0`

`typedef struct record`

`{`

`int info;`

`struct record *link;`

`}listrecord,*listpointer;`

`typedef listpointer pointerarray[21];`

`pointerarray ptr,pred;`

`listpointer p;`

`main()`

`/* Driver for permutations. */`

`{`

`int n;`

`printf("\n n = ?\n");`

`scanf("%d",&n);`

`permutations(n);`

`}`

`permutations(n)`

`/* Generates and processes each`

`permutation of the integers 1 to n.`

`*/`

`int n;`

`{`

`int done;`

`done = FALSE;`

`initialize(n);`

`while (!done)`

`{`

`process(n);`

`next(n,&done);`

`}`

`}`

`initialize(n)`

`/* Creates initial permutation */`

`int n;`

`{`

`int i;`

`listpointer q;`

`p = malloc(sizeof(listrecord));`

`q = P;`

`for (i=1;i<=n;i++)`

`{`

`q->link = malloc(sizeof(listrecord));`

`q = q->link;`

`q->info = n - i + 1;`

`ptr[n-i+1] = q;`

`pred[i] = p;`

`}`

`q->link = NULL;`

`}`

`process(n)`

`/* Prints the current permutation */`

`int n;`

`{`

`listpointer q;`

`q = p->link;`

`while (q != NULL)`

`{`

`printf("\n%d\n",q->info);`

`q = q->link;`

`}`

`printf("\n");`

`}`

`next(n,pdone)`

`/* Generates the next permutation unless`

`the current one is the last. In this case`

`done is set to true.`

`*/`

`int n,*pdone;`

`{`

`if (n > 1)`

`if (ptr[n]->link != NULL)`

`{`

`pred[n]->link = ptr[n]->link;`

`pred[n] = pred[n]->link;`

`ptr[n]->link = pred[n]->link;`

`pred[n]->link = ptr[n];`

`}`

`else`

`{`

`pred[n]->link = NULL;`

`next(n-1,pdone);`

`ptr[n]->link = p->link;`

`p->link = ptr[n];`

`pred[n] = p;`

`}`

`else`

`*pdone = TRUE;`

`}`

# 4.3: A Close Look at the Execution of Recursive Programs

Parameters passed to a function by value also specify storage that is not local to it, but these parameters are treated differently. When the component is invoked, their values are copied into storage that is local to the component. It is these local copies that are referenced, and perhaps changed, by the component as it executes, but such changes are not reflected back to the original values. In this way the information passed by value is made accessible to the component, which may even change the local copies, but such changes are kept local; the original nonlocal values are untouched.

The component may, in turn, invoke another component, which may invoke still another, and so on. Each time this is done, the calling component suspends its operation, so all components of the sequence, except the last, are waiting.

When the last component completes its task, the component that invoked it then continues. In order for this to happen, each component must remember from whence it was called. Also, upon return to the correct place, the scratchpad of the calling component must be the same as before the call. For nonrecursive programs, the important point is that each component must retain only one returning point, and the scratchpad of a component is automatically retained when it invokes another component.

With recursive programs the situation is considerably different, as evidenced by Figures 4.2, 4.4, and 4.6. First, when a recursive function is invoked, this may be the initial, first, second, or nth recursive call to it. If it is the nth recursive call, there may be as many as (n + 1) returning places to be retained, not just one. Second, there may be (n + l) scratchpads to be retained. How many there are is determined by the number of calls that are currently suspended.

#### Figure 4.7 Data and Scratchpad for a Component

In Figure 4.2, when the tenth recursive call (k = 3) is made to towers, there are three returns and three sets of scratchpads to remember in addition to the initial call's return.

`[2] and n = 4, i = l, a = 2, f = 3 for the initial call`

`[1] and n = 3, i = 2, a = 1, f = 3 for the eighth recursive call`

`[1] and n = 2, i = 2, a = 3, f = 1 for the ninth recursive call`

n = 1, i = 2, a = 1, f = 3 for the tenth recursive call are stored, by our assumption, local to towers. In general, the depth of recursion will be n - l. Using our terminology, there are no data.

In Figure 4.4, when the third recursive call is made to copy, there are three returns and three sets of scratchpads to be retained beside the initial call's return:

`first0, null0, rest0 for the initial call`

`first1, null1, rest1 for the first recursive call`

`first2, null2, rest2 for the second recursive call`

No returns are shown since they all return to the same place: the statement setlink(*psecond, rest). The depth of the recursion is one less than the length of the list to be copied. The data for the initial call is second, while for the (n + 1)th recursive call it is restn. A change to rest in the (n + 1)th call is reflected in the scratchpad for the nth call. Storage could be saved by making null global to copy.

In Figure 4.6 the situation corresponds to a point in the initial call when the second and then the third recursive calls to next are made. The local variable i is not shown, and the three scratchpad values are

`n = 4 for the initial call`

`n = 3 for the second recursive call`

`n = 2 for the third recursive call`

Again, the returns are all the same, to the statement following the recursive call to next, so they are not shown. The depth of the recursion is n - 1. The data consist of p, ptr, pred, and done.

It should by now be clear that the storage required by a recursive function is proportional to its depth. The execution time, on the other hand, has to do with the total number of recursive calls that are required to complete the initial call. This explains why the recursive solution to Counting Squares (Section 4.2.6) is so inefficient both in time and in storage.

# 4.4: Implementing Recursive Programs

The programmer constrained to a nonrecursive language can still use the power of recursion. This is done by writing a program as if the language allowed recursion, and then translating the program into an equivalent nonrecursive program. This is what compilers for recursive languages do and is one reason for spending time finding out how to translate (or implement) a recursive program.

As shown in the discussion of Counting Squares, some problems should not be solved using recursion under any circumstances. Sometimes, as in the Towers of Hanoi problem, we may only be able to think of a recursive solution. Often we can find both a recursive and a nonrecursive solution, which may be compared for trade-offs in clarity, conciseness, storage, and execution time.

Even though a recursive solution may not be best, it may suggest an approach to the problem that otherwise might have been missed and that may turn out to be the most desirable. In fact, the translated version of a recursive solution can often be helpful in finding desirable modifications. This is another reason for looking at the translation process.

Normally, if a recursive approach is right for a problem, and is applied intelligently, further refinements of the program do not improve its efficiency significantly. Breaking up a problem as required by the recursive approach does, however, create the possibility of doing certain tasks in parallel. For instance, the three components of the Towers of Hanoi solution may all be done at the same time with parallel processing. Languages and computer systems that allow concurrent processing will surely become more prevalent. When they do, recursive solutions will have another advantage.

If each successive call to a recursive function were implemented so that during execution a new copy of the function is created with its own storage for the return and its scratchpad values, then, in effect, the function could be treated like any function in a nonrecursive program. With the advent of cheaper and larger storage, this may well occur in the future, but until then, another means of managing the generated returns and scratchpad values is needed.

The essential difference between nonrecursive (or iterative) programs and recursive programs is the storage needed for the returns and scratchpad values of the latter. Figures 4.2, 4.4, and 4.6 actually represent the bookkeeping needed to simulate the execution of a recursive program. The basic idea in translating such programs is to implement this bookkeeping procedure as follows:

1. Each time a recursive call is made to the function,

a. save the proper return place and the current scratchpad values,

b. set the scratchpad values to their new values.

2. Each time a recursive call is completed,

a. restore the current return and scratchpad values to those that were last saved (and save them no longer),

b. return to the proper place in the recursive function, or to the original calling component if it is the initial call that has just finished.

This procedure does not apply to a function that returns a value, but it may be modified to do so. Or the function may be modified to return the value in an additional parameter passed by pointer. As an illustration of this, the first version of copy might be obtained by such a modification of the second.

Notice that the information to be retained (return and scratchpad values) must be recalled in the order opposite to the order in which it is generated. This is no different for nonrecursive programs, except that then the information is saved locally with each component. It is helpful to think of return and scratchpad values as the entries of a record. Then the collection of records corresponding to each suspended recursive call must be stored in some data structure. The data structure must retain not only these records, but also the correct order.

In step 1 above, the record to be saved must become the new first record in the order. In step 2, the current first record (the last saved) must be removed from the data structure. A data structure for storing information so that new information can be inserted, so that a deletion always removes the last piece of information inserted, and which can be tested to see if it is empty (contains no information) is called a stack. Stacks will be discussed in more detail later in the chapter; for now they will simply be used.

## 4.4.1 A Sample Implementation of Towers

Recursive Version

`towers(n,i,a,f)`

`/* Moves the top n disks`

`from peg i to peg f`

`*/`

`int n,i,a,f;`

`{`

`if(n == 1)`

`printf("\n %d -> %d\n",i,f);`

`else`

`{`

`towers(n-1,i,f,a);`

`printf("\n %d -> %d\n",i,f)`

`towers(n-1,a,i,f);`

`}`

`}`

Nonrecursive Version

`towers(n,i,a,f)`

`/* Moves the top n disks`

`from peg i to peg f`

`*/`

`int n,i,a,f;`

`{`

`int retrn;`

`stack s;`

`setstack(&s);`

`one: if(n == 1)`

`printf("\n %d -> %d\n",i,f);`

`else`

`{`

`s_tack(1,n,i,a,f &s);`

`setvar1(&n,&i,&a,&f);`

`goto one;`

`}`

`two: if(!empty(&s))`

`{`

`restore(&retrn,&n,&i,&a,&f,&s);`

`switch(retrn)`

`{`

`case 1:`

`printf("\n %d -> %d\n",`

`i,f)`

`s_tack(2,n,i,a,f,&s);`

`setvar2(&n,&i,&a,&f);`

`goto one;`

`case 2:`

`goto two;`

`}`

`}`

`}`

Setvar1(&n,&i,&a,&f) sets n to n - 1 and interchanges the values of f and a.

Setvar2(&n,&i,&a,&f) sets n to n - 1 and interchanges the values of a and i.

The "implicit" exit of the recursive program (after the second recursive call) has been replaced in the implementation by a complex "explicit" sequence of statements. This is because the exit must, in effect, transfer control to the proper place in the calling program. If the stack itself is empty at this point, this means that it is the initial call to towers that has been completed. Return should then be to the calling program. Otherwise, it is some recursive call to towers that has been completed. At this point, the top stack record contains the four scratchpad values to be restored and the return location in towers.

You should simulate the execution of this implementation to see that it really works correctly. The statement labeled "one" corresponds to the first executable statement of the recursive program; this is the statement that is invoked in the implementation to represent a recursive call. It is only invoked, however, after the scratchpad values of the current call and proper return location have been saved on the stack, and the scratchpad values for the upcoming recursive call have been correctly set.

This example highlights the fact that considerable overhead is involved in executing recursive programs. Time is consumed because variables must be stacked and unstacked for each recursive call and its return. It is often possible to discover a more efficient nonrecursive algorithm for a problem, even though the recursive algorithm is evident, as was done in Counting Squares. Nonetheless, the recursive version is frequently clearer, easier to understand, and more concise, as well as easier to verify. Therefore some programmers prefer recursive solutions to problems, even if they are less efficient than the nonrecursive versions.

Another approach is to attempt to increase the efficiency of the iterative program (the implementation) that is translated from a recursive program. This attempt can be made whether or not there is a competing nonrecursive routine.

Notice that in the case statement for retrn at 1, the call to s_tack(2,n,i,a,f,&s) saves the values of the current variables in the suspended call, in order to make the recursive call to towers(n-1,a,i,f). When this new recursive call is completed, these current values will be restored, and the retrn will be 2. The statement labeled "two" will then be executed.

If the stack is empty, the initial call is complete. Otherwise restore will be called immediately and control transferred to the new value of retrn. The current values saved by s_tack(2,n,i,a,f,&s) will never be used, and so need not be saved at all. Thus the call to s_tack( 2,n,i,a,f,&s ) may be eliminated from the program. This means that the only return code appearing will be l in the call to s_tack(1,n,i,a,f,&s). However, the value of retrn after restore is called will always be 1. Therefore, no return code needs to be stored on the stack; the case structure may be removed. Retrn is not needed at all. This new program then looks like the following.

Second Nonrecursive Version

`towers(n,i,a,f)`

`/* Moves the top n disks`

`from peg i to peg f`

`*/`

`int n,i,a,f;`

`{`

`stack s;`

`setstack(&s);`

`one: if(n == 1)`

`printf("\n %d -> %d\n",i,f);`

`else`

`{`

`s_tack(n,i,a,f,&s);`

`setvar1(&n,&i,&a,&f);`

`goto one;`

`}`

`if(!empty(&s))`

`{`

`restore(&n,&i,&a,&f,&s);`

`printf("\n %d -> %d\n",i,f);`

`setvar2(&n,&i,&a,&f);`

`goto one;`

`}`

`}`

Another improvement can be made by changing the if-else structure to a while loop. Doing so improves the clarity and eliminates the goto:

`one: if(n == 1)                    one: while(n > 1)`

`printf("\n %d -> %d\n",i,f);          {`

`else                                          s_tack(n,i,a,f,&s);`

`{                                         setvar1(&n,&i,&a,&f);`

`s_tack(n,i,a,f,&s);                 }`

`setvar1(&n,&i,&a,&f);            printf("\n %d -> %d\n",i,f);`

`goto one;`

`}`

This yields

Third Nonrecursive Version

`towers(n,i,a,f)`

`/* Moves the top n disks`

`from peg i to peg f`

`*/`

`int n,i,a,f;`

`{`

`stack s;`

`one: while(n > 1)`

5 while loop replaces if-else construct

`{`

`s_tack(n,i,a,f,&s);`

`setvar1(&n,&i,&a,&f);`

`}`

`printf("\n %d -> %d\n",i,f);`

`if(!empty(&s))`

`{`

`restore(&n,&i,&a,&f,&s);`

`printf("\n %d -> %d\n",i,f);`

`setvar2(&n,&i,&a,&f);`

`goto one;`

`}`

`}`

Finally, the function can be written in more structured form, as follows:

Final Nonrecursive Version

`towers(n,i,a,f)`

`/* Moves the top n disks`

`from peg i to peg f`

`*/`

`int n,i,a,f;`

`{`

`stack s;`

`int done`

`done = FALSE;`

`while(!done)`

`{`

`while(n > 1)`

`{`

`s_tack(n,i,a,f,&s);`

`setvar1(&n,&i,&a,&f);`

`}`

`printf("\n %d -> %d\n",i,f);`

`if(!empty(&s))`

`{`

`restore(&n,&i,&a,&f,&s);`

`printf("\n %d -> %d\n",i,f);`

`setvar2(&n,&i,&a,&f);`

`}`

`else`

`done = TRUE;`

`}`

This structured version is more efficient than the compilerlike direct translation because the number of stack operations has been reduced. It is also structured for clarity in reading. Both changes make it a better implementation.

## 4.4.2 A Sample Implementation for Permutations

Nonrecursive Version

`next(n,pdone)`

`/* Generates the next permutation unless`

`the current one is the last. In this case`

`done is set to true.`

`*/`

`int n,*pdone;`

`{`

`int i,retrn;`

`stack s;`

`one: if(n > 1)`

`if(l[n] < n)`

`{`

`p[l[n]] = p[l[n] + 1];`

`p[l[n] + 1] = n;`

`l[n] = l[n] + 1;`

`}`

`else`

`{`

`s_tack(1,n,i,&s);`

`setvar(&n,&i);`

`goto one;`

`}`

`else`

`*pdone = TRUE;`

`two: if(!empty(&s))`

`{`

`restore(&retrn,&n,&i,&s);`

`switch(retrn)`

`{`

`case 1:`

"explicit" exit must be made

`{`

`for(i=n-1;i>=1;i--)`

`p[i+1] = p[i];`

`p[1] = n;`

`l[n] = 1;`

`goto two;`

`{`

`{`

`{`

`{`

where setvar(&n,&i) simply sets n to n-1.

The same program can be written in a more structured way. First notice that the statement labeled "two" and the goto "two" statement create a while loop. Introducing that while loop but retaining the structure of "one," the overall structure of the program becomes as follows

`one: if c1 then`

`if c2 then`

`task c1 and c2 both true`

`else`

`task for c1 true but c2 false`

`goto one`

`else`

`task for c1 false`

`while not empty(&s)`

`loop task`

Next, the structure of "one" can also be improved, as follows.

`while (c1 and not c2)`

`task for c1 true but c2 false`

`if c1, then`

`task for c1 and c2 both true`

`else`

`task for c1 false`

`while not empty (&s)`

`loop task.`

Second Nonrecursive Version

`next(n,pdone)`

`/* Generates the next permutation unless`

`the current one is the last. In this case`

`done is set to true.`

`*/`

`int n,*pdone`

`{`

`int i,retrn;`

`stack s;`

`while((n > 1) && !(l[n] < n))`

`{`

`s_tack(1,n,i,&s);`

`setvar(&n,&i);`

`}`

`if(n > 1)`

`{`

`p[l[n]] = p[l[n] + 1];`

`p[l[n] + 1] = n;`

`l[n] = l[n] + 1;`

`}`

`else`

`*pdone = TRUE;`

`while(!empty(&s))`

`{`

`restore(&retrn,&n,&i,&s);`

`switch(retrn)`

`{`

`case 1:`

`{`

`for(i=n-1;i>=1;i--)`

`p[i+1] = p[i];`

`p[1] = n;`

`l[n] = 1;`

`}`

`}`

`}`

`}`

In general, when the value of a scratchpad variable does not change or does not need to be maintained between recursive calls, it need not be stacked. This is the case with the variable i of next. Also, when there is only one return place from a recursive call, there is no need to stack a return indicator. This is the situation with next. Finally, the value of n varies in a predictable fashion. Its restored value will always be 1 greater than its current value. Thus there is no need to stack n. Each time a recursive call returns, n may be correctly restored by adding 1 to its current value.

Therefore, the stack is unnecessary, since no information must be retained on it. The s_tack function can be removed, setvar can be replaced by the statement n = n-1, and restore can be replaced by the statement n = n+1. Still, the stack controls the second while loop in our translated version. Even though no information needs to be stacked, it is still necessary to know when the stack would have been empty so that the loop may be properly exited.

Notice that the first while loop decreases n by l every time a stack entry would have been made, and the second while increases n by l every time an entry would have been deleted from the stack. Hence, if an integer variable s is set to n initially, prior to the first while loop, the test to see if the stack is empty in the second while loop becomes s = n. The final version of next is an iterative program that has no stack. It is an example of the translated version giving us a better solution. This four-step solution is efficient and is also clear.

1. Set s to n.

2. Set n to the rightmost entry in the permutation that can still be shifted right.

3. If that entry is not l, then

Shift it right

else

Set done to true

4. Place the s-n entries that could not be moved to the right in the proper order at the left end of the permutation.

Final Nonrecursive Version

`next(n,pdone)`

`/* Generates the next permutation unless`

`the current one is the last. In this case`

`done is set to true.`

`*/`

`int n,*pdone`

`{`

`int i,s;`

`1. s = n;`

`2. while((n > 1) && !(l[n] < n))`

`n--;`

`3. if(n > 1)`

`{`

`p[l[n]] = p[l[n] + 1];`

`p[l[n] + 1] = n;`

`l[n] = l[n] + 1;`

`}`

`else`

`*pdone = TRUE;`

`4. while(s > n)`

`{`

`n++`

`for(i=n-1;i>=1;i--)`

`p[i+1] = p[i];`

`p[1] = n;`

`l[n] = 1;`

`}`

`}`

# 4.5: Stacks

The stack, with the operations of front-end insertion and deletion, initialization, and an empty check, is a data abstraction. Stacks used to be called "pushdown stacks"; insertion of data onto the stack was referred to as "pushing" the stack, and deleting data was known as "popping" the stack. So far we have written programs that treat the stack with the four operations as a data abstraction. Stacks will be used frequently in algorithms developed throughout the rest of this book, and it is now time to consider this implementation. Of the many implementations possible for the stack, the following subsections illustrate the three most straightforward.

## 4.5.1 Array Implementation of a Stack

`typedef struct`

`{`

`whatever info;`

`}stackrecord;`

`typedef struct`

`{`

`stackrecord stackarray [LIMIT];`

`int top;`

`}stack;`

`stack s;`

The definitions must be preceded by a typedef for "whatever." Let us assume LIMIT has been set in a define statement fixing the maximum number of items the stack can hold. Suppose 6, 45, 15, 32, and 18 were pushed onto the stack. Figure 4.8 illustrates the meaning attached to the declaration. Figure 4.8(a) is a conceptualization of the stack. Since 6 was the first entry on the stack, it is on the bottom. Likewise, 18 was the last entry, so it is on top. Figure 4.8(b) is the way the data is stored in the actual stack s. The stackarray holds the data and top contains an index to the current entry on the top of the stack. Although 6 is at the top of the array, it is the bottom stack entry; while 18 is at the bottom of the array, it is the top stack entry. Thus top has the value 4.

Addition or insertion of a new element to the stack will be accomplished by a function push. Removal or deletion of the current top stack element will be accomplished by a function pop. Executing push (&newrecord,&s) results in the contents of newrecord being placed on the stack as a new first element. A call to the function pop(&s,&value) causes the removal of the current top stack element, with value containing a copy of that value. A routine setstack sets the stack to empty so that it initially contains no entries.

Suppose we execute

`pop(&s,&y);`

`pop(&s,&z);`

`push(&newrecord,&s);`

If Figure 4.8 indicates the current stack, then Figure 4.9 shows the new situation after this execution.

#### Figure 4.9 Stack after Insertion of a New Element

These routines may be implemented as follows:

`setstack (ps)`

`/* Initializes the stack s to empty */`

`stack *ps;`

`{`

`(*ps).top = -1;`

`}`

`empty (ps)`

`/* Returns true only if the stack is empty */`

`stack *ps;`

`{`

`return ((*ps).top == -1);`

`}`

`push (pnewrecord,ps)`

`/* Inserts the record newrecord`

`at the top of the stack s`

`*/`

`stackrecord *pnewrecord,`

`stack *ps;`

`{`

`if ((*ps).top == (LIMIT - 1))`

`overflow(ps);`

`else`

`{`

`(*ps).top = (*ps).top + 1;`

`(*ps).stackarray[(*ps).top].info =`

`(*pnewrecord).info;`

`}`

`}`

`pop(ps,pvalue)`

`/* Copies the contents of the top record`

`of stack s into value and removes the`

`record from the stack`

`*/`

`stack *ps;`

`stackrecord *pvalue;`

`{`

`if(empty(ps))`

`underflow(ps);`

`else`

`{`

`(*pvalue).info = (*ps).stackarray`

`[(*ps).top].info;`

`(*ps).top = (*ps).top - 1;`

`}`

`}`

The procedures overflow and underflow are assumed to take appropriate action when they are invoked. Notice that the elements of the stack will be of "whatever" type. We have taken the liberty here of assuming that the C compiler being used allows the contents of one structure to be assigned to another. Otherwise, for example, the assignment

`(*ps).stackarray[(*ps).top].info =`

`(*pnewrecord).info;`

that occurs in push could not be used. Instead, each field of info would have to be individually assigned.

`typedef struct`

`{`

`whatever stackarray [LIMIT];`

`int top;`

`}stack;`

`push(value,ps)`

`/* Inserts the new value`

`at the top of the stack s`

`*/`

`whatever value;`

`stack *ps;`

`{`

`if((*ps).top == (LIMIT-1))`

`overflow(ps);`

`else`

`{`

`(*ps).top = (*ps).top + 1;`

`(*ps).stackarray[(*ps).top] = value;`

`}`

`}`

`pop(ps,pvalue)`

`/* Copies the contents of the top entry`

`of stack s into value and removes it`

`from the stack`

`*/`

`stack *ps;`

`whatever *pvalue;`

`{`

`if(empty(ps))`

`underflow(ps);`

`else`

`{`

`*pvalue = (*ps).stackarray[(*ps).top];`

`(*ps).top = (*ps).top - 1;`

`}`

`}`

"Whatever" will, of course, be declared of type int, or float, etc. The same simplification can be made, when appropriate, to the implementations of Sections 4.5.2, 4.5.3, 4.7.1, 4.7.2, and 4.7.3.

An application of the stack to the nonrecursive towers of Section 4.4.1 follows. It illustrates the use of the stack and its treatment as a data abstraction.

`#include <stdio.h>`

`#define LIMIT 50`

`typedef struct`

`{`

`int n;`

`int i;`

`int a;`

`int f;`

`}whatever;`

`typedef struct`

`{`

`whatever info;`

`}stackrecord;`

`typedef struct`

`{`

`stackrecord stackarray [LIMIT];`

`int top;`

`}stack;`

`setstack(ps)`

`/* Initializes the stack s to empty */`

`stack *ps;`

`{`

`(*ps).top = -1;`

`}`

`empty(ps)`

`/* Returns true only if the stack s is empty */`

`stack *ps;`

`{`

`return((*ps).top == -1);`

`}`

`push(pnewrecord,ps)`

`/* Inserts the record newrecord`

`at the top of the stack s`

`*/`

`stackrecord *pnewrecord;`

`stack *ps;`

`{`

`if ((*ps).top == (LIMIT-1))`

`overflow(ps);`

`else`

`{`

`(*ps).top = (*ps).top + 1;`

`(*ps).stackarray[(*ps).top].info =`

`(*pnewrecord).info;`

`}`

`}`

`pop(ps,pvalue)`

`/* Copies the contents of the top record`

`of stack s into value and removes the`

`record from the stack`

`*/`

`stack *ps;`

`stackrecord *pvalue;`

`{`

`if (empty(ps))`

`underflow(ps);`

`else`

`{`

`(*pvalue).info =`

`(*ps).stackarray[(*ps).top].info;`

`(*ps).top = (*ps).top - 1;`

`}`

`}`

`overflow(ps);`

`/* Prints a message that the stack has overflowed */`

`stack *ps;`

`{`

`printf(" The stack has overflowed \n");`

`}`

`underflow(ps);`

`/* Prints a message that the stack has underflowed */`

`stack *ps;`

`{`

`printf(" The stack has underflowed \n");`

`}`

`main()`

`/* Driver for towers */`

`{`

`int n;`

`printf("\n enter a value for n\n");`

`scanf("%d",&n);`

`towers(n,1,2,3);`

`}`

`towers(n,i,a,f)`

`/* Moves the top n disks`

`from peg i to peg f`

`*/`

`int n,i,a,f;`

`{`

`stack s;`

`int done;`

`setstack(&s);`

`done = FALSE;`

`while(!done)`

`{`

`while (n > 1)`

`{`

`s_tack(n,i,a,f,&s);`

`setvar1(&n,&i,&a,&f);`

`}`

`printf("\n %d -> %d\n",i,f);`

`if(!empty(&s))`

`{`

`restore(&n,&i,&a,&f,&s);`

`printf("\n %d -> %d\n",i,f);`

`setvar2(&n,&i,&a,&f);`

`}`

`else`

`done = TRUE;`

`}`

`setvar1(pn,pi,pa,pf)`

`/* Sets n to n-1 and`

`interchanges f and a`

`*/`

`int *pn,*pi,*pa,*pf;`

`{`

`int t;`

`*pn = *pn-1;`

`t = *pf;`

`*pf = *pa;`

`*pa = t;`

`}`

`setvar2(pn,pi,pa,pf)`

`/* Sets n to n-1 and interchanges a and i`

`*/`

`int *pn,*pi,*pa,*pf;`

`{`

`int t;`

`*pn = *pn-1;`

`t = *pa;`

`*pa = *pi;`

`*pi = t;`

`}`

`s_tack(n,i,a,f,ps)`

`/* Creates a record containing`

`n,i,a, and f and inserts it`

`on stack s`

`*/`

`int n,i,a,f;`

`stack *ps;`

`{`

`stackrecord newrecord;`

`newrecord.info.n = n;`

`newrecord.info.i = i;`

`newrecord.info.a = a;`

`newrecord.info.f= f;`

`push(&newrecord,ps);`

`}`

`restore(pn,pi,pa,pf,ps)`

`/* Removes the top record from`

`stack s and copies its contents`

`into n,i,a,f`

`*/`

`int *pn,*pi,*pa,*pf;`

`stack *ps;`

`{`

`stackrecord value;`

`pop(ps,&value);`

`*pn = value.info.n;`

`*pi = value.info.i;`

`*pa = value.info.a;`

`*pf = value.info.f;`

`}`

In review of the program, notice that it treates the stack as a data abstraction. The type definitions and function definitions for the stack are placed at the top of the program. The functions setvar, s_tack, and restore are not basic stack operations; they are used by towers. Thus they have been placed after towers. Similarly, towers has been placed after main. Also, s_tack and restore are dependent on the stack implementation, since they must know the structure of a stack record, which is, in turn, determined by the needs of towers for its scratchpad.

## 4.5.3 List Implementation of the Stack with Records in Dynamic Memory

The third stack implementation is also as a list--one that involves dynamic storage allocation of the records. That is, the records are stored in the storage area set aside by C to store records referenced by pointer variables. First, the following declaration must be made.

`typedef struct record`

`{`

`struct whatever info;`

`struct record *link;`

`}stackrecord,*stack;`

If we then define s as type stack, code can be written that is independent of its implementation. Setstack must initialize the stack to empty. This means setting s, the head of the list implementing the stack, to null. Push must now use malloc to allocate storage for the entry to be pushed onto the stack before setting its info field and inserting that record as the new first record on the stack. Pop must copy the info field value of the top record into value and then delete that record from the stack.

These stack operations are implemented as follows.

`setstack(ps)`

`/* Initializes the stack s to empty */`

`stack *ps;`

`{`

`*ps = NULL;`

`}`

`empty(ps)`

`/* Returns true only if the stack s is empty */`

`stack *ps;`

`{`

`return(*ps == NULL);`

`}`

`push(pnewrecord,ps)`

`/* Inserts the record newrecord`

`at the top of the stack s`

`*/`

`stackrecord *pnewrecord;`

`stack *ps;`

`{`

`stackrecord *newentry;`

`newentry = malloc(sizeof(stackrecord));`

`newentry->info = pnewrecord->info;`

`newentry->link = *ps;`

`*ps = newentry;`

`}`

`pop(ps,pvalue)`

`/* Copies the contents of the top record`

`of stack s into value and removes the`

`record from the stack`

`*/`

`stack *ps;`

`stackrecord *pvalue;`

`{`

`if(!empty(ps))`

`{`

`pvalue->info = (*ps)->info;`

`*ps = (*ps)->link;`

`}`

`else`

`underflow(ps);`

`}`

Notice that this implementation removes the artificial restriction imposed by LIMIT in the first implementation using an array. This is one of the advantages of using dynamic allocation by means of pointer variables.

It is very important to see that no matter what the implementation, as long as the stack is treated as a data abstraction when writing programs, the programs need not be changed, even if the programmer decides to change the implementation of the stack. Only the declarations and definitions related to the stack need be changed, as is evident in the following nonrecursive towers that uses the list implementation. It should be compared to the program of Section 4.5.1, in which the stack was implemented using an array.

`#include <stdio.h>`

`#define NULL 0`

`typedef struct`

`{`

`int n;`

`int i;`

`int a;`

`int f;`

`}whatever;`

`typedef struct record`

`{`

`whatever info;`

`struct record *link;`

`}stackrecord, *stack;`

`setstack(ps)`

`/* Initializes the stack s to empty */`

`stack *ps;`

`{`

`*ps = NULL;`

`}`

`empty(ps)`

`stack *ps;`

`{`

`return(*ps == NULL);`

`}`

`push(pnewrecord,ps)`

`stackrecord *pnewrecord;`

`stack *ps;`

`{`

`stackrecord *newentry;`

`newentry = malloc(sizeof(stackrecord));`

`newentry->info = pnewrecord->info;`

`newentry->link = *ps;`

`*ps = newentry;`

`}`

`pop(ps,pvalue)`

`/* Copies the contents of the top record`

`of stack s into value and removes the`

`record from the stack`

`*/`

`stack *ps;`

`stackrecord *pvalue;`

`{`

`if(!empty(ps))`

`{`

`pvalue->info = (*ps)->info;`

`*ps = (*ps)->link;`

`}`

`else`

`underflow(ps);`

`}`

`overflow(ps);`

`/* Prints a message that the stack has overflowed */`

`stack *ps;`

`{`

`printf(" The stack has overflowed \n");`

`}`

`underflow(ps);`

`/* Prints a message that the stack has underflowed */`

`stack *ps;`

`{`

`printf(" The stack has underflowed \n");`

`}`

`main()`

`/* Driver for towers */`

`{`

`int n;`

`printf("\n enter a value for n \n");`

`scanf("%d",&n);`

`towers(n,1,2,3);`

`}`

`towers(n,i,a,f)`

`1 final nonrecursive version`

`/* Moves the top n disks`

`from peg i to peg f`

`*/`

`int n,i,a,f;`

`{`

`stack s;`

`1 allocates storage for s (an instance of type stack)`

`int done`

`setstack(&s);`

`done = FALSE;`

`while(!done)`

`{`

`while (n > 1)`

`{`

`s_tack(n,i,a,f,&s);`

`setvar 1(&n,&i,&a,&f);`

`}`

`printf("\n %d -> %d\n",i,f);`

`if(!empty(&s))`

`{`

`restore(&n,&i,&a,&f,&s);`

`printf("\n %d -> %d\n",i,f);`

`setvar2(&n,&i,&a,&f);`

`}`

`else`

`done = TRUE;`

`}`

`setvar1(pn,pi,pa,pf)`

`/* Sets n to n - 1 and`

`interchanges f and a`

`*/`

`int *pn,*pi,*pa,*pf;`

`{`

`int t;`

`*pn = *pn - 1;`

`t = *pf;`

`*pf = *pa;`

`*pa = t;`

`}`

`setvar2(pn,pi,pa,pf)`

`/* Sets n to n - 1 and`

`interchanges a and i`

`*/`

`int *pn,*pi,*pa,*pf;`

`{`

`int t;`

`*pn = *pn - 1;`

`t = *pa;`

`*pa = *pi;`

`*pi = t;`

`}`

`s_tack(n,i,a,f,ps)`

`/* Creates a record containing`

`n, i, a, and f and inserts it`

`on stack s`

`*/`

`int n,i,a,f;`

`stack *ps;`

`{`

`stackrecord newrecord;`

`newrecord.info.n = n;`

`newrecord.info.i = i;`

`newrecord.info.a = a;`

`newrecord.info.f = f;`

`push(&newrecord,ps);`

`}`

`restore(pn,pi,pa,pf,ps)`

`/* Removes the top record from`

`stack s and copies its contents`

`into n,i,a,f`

`*/`

`int *pn,*pi,*pa,*pf;`

`stack *ps;`

`{`

`stackrecord value;`

`pop(ps,&value);`

`*pn = value.info.n;`

`*pi = value.info.i;`

`*pa = value.info.a`

`*pf = value.info.f;`

`}`

# 4.6: Evaluation and Translation of Expressions

(((a + (b/c * d)) + (a/w)) * b)/(((a * c) + d) + a)

#### Table 4.1 Notations for Two

`Arithmetic Expressions`

`          a + (b * c)   (a + b) * c`

`Prefix    + a * bc      * + abc`

`Infix     a + b * c     a + b * c`

`Postfix   abc * +       ab + c *`

Even humans must scan such an expression carefully, more than once, before discovering that its basis syntactic structure is (operand 1)/(operand 2). A serious problem for the compiler writers was how to translate such expressions without making many scans back and forth through them. The problem was compounded further because programmers were not required to write fully parenthesized expressions; this created the additional dilemma of how to resolve ambiguity. As will be shown below, ambiguity may be resolved by using a notation other than infix.

## 4.6.1 Postfix Expressions

Given an infix expression that is completely parenthesized, such as

`((a + b) * (c/d))`

you know how to evaluate it. This is because you have grown accustomed to the rules for its evaluation, although you might be hard pressed to state those rules completely and precisely. In any case, parentheses signal how the operators are to be applied to the operands, indicating that (a + b) and (c/d) must be evaluated first before applying the * operator. Removing all parentheses yields

`a + b * c/d`

Unless conventions or rules are given, this expression is ambiguous. Its five distinct interpretations correspond to the ways in which parentheses may be placed:

`((a + b) * (c/d))`

`(((a + b) * c)/d)`

`((a + (b * c))/d)`

`(a + ((b * c)/d))`

`(a + (b * (c/d)))`

A postfix expression such as

`ab + cd/*`

makes little sense, for you are not used to it, having little experience in interpreting or evaluating it. The rule to be used is as follows:

1. Scan the postfix expression from left to right.

2. Whenever an operator is encountered,

replace it, and the immediately preceding number of operands required by that operator, with the result of applying that operator to those operands.

3. Treat this replacement as an operand, and continue scanning from this point.

Thus the postfix expression is equivalent to the infix expression

`((a + b) * (c/d))`

The rule, in generating this expression, produces the two intermediate expressions: (a + b)cd/*, (a + b)(c/d)*.

The following list shows the five fully parenthesized infix expressions representing the interpretations of a + b * c/d and their corresponding postfix expressions.

`((a + b) * (c/d)) .... ab + cd/*`

`(((a + b) * c)/d) .... ab + c * d/`

`((a + (b * c))/d) .... abc* + d/`

`(a + ((b * c)/d)) .... abc*d/+`

`(a + (b * (c/d))) .... abcd/*+`

These examples emphasize two points:

1. The rule for evaluating postfix expressions allows no ambiguity. It determines precisely the meaning or interpretation of the postfix expression.

2. An infix expression, unless fully parenthesized, may be ambiguous in its meaning or interpretation.

It is because of statement 1 that postfix notation, or postfix expressions, are called parentheses-free. A similar rule allows prefix notation, or prefix expression, to be parentheses-free .

Furthermore, evaluation of a postfix expression is easily accomplished by scanning the expression from left to right and using a stack to retain operands and

#### Table 4.2 Evaluation of a Postfix Expression

`Input      Operand Stack`

`  a        a`

`  b        b`

`           a`

`  c        c`

`           b`

`           a`

`  *        (b * c)`

`           a`

`  d        d`

`           (b * c)`

`           a`

`  /        ((b * c)/d)`

`           a`

`  +        (a + ((b * c)/d)`

results of intermediate evaluations. Any operand that is encountered is placed on an operand stack. When an operator is encountered, its operands are taken from the top of the stack, the operator is applied, and the result is put on the top of the stack. The process is illustrated in the following example.

Table 4.2 shows the contents of the operand stack after each input is processed, simulating the procedure for evaluation of a postfix expression. The expression is ABC*D/+.

Since the procedure for the evaluation of an arithmetic expression using a stack is relatively straightforward and requires no parentheses, why don't programmers write arithmetic expressions in postfix notation only? It is because they are so used to infix notation that they don't want to change. As a result, high-level languages accept infix expressions rather than postfix. This leads back to the question of how infix expressions may be evaluated.

## 4.6.2 Infix Expressions

1. Scan the infix expression from left to right.

2. When a "matched" pair of ''left" and "right" parentheses is encountered,

apply the operator to the operands enclosed within the pair of parentheses, and replace the paired parentheses and the contained operator and operands by the result. Continue scanning from this point.

One problem remains: How do we evaluate infix expressions that are not completely parenthesized? Recall that there are standard rules for interpreting infix expressions in this case. These rules are also incorporated in high-level languages. They are necessary because parentheses are not always available to signal what is to be done next. For example, if we evaluate

`a + b * c/d`

then when the * is encountered, the stacks appear as

`Operand Stack     Operator Stack`

`--------------------------------`

`      b                 +`

`      a`

1. Exponentiation (**) has the highest priority.

2. Multiplication and division (*, /) have the same priority, which is higher than that of addition or subtraction (+, -).

3. Addition and subtraction (+, -) have the same priority.

A left parenthesis also needs a priority, the lowest.

Whether b is an operand of * or + can then be resolved by taking b as an operand of the highest priority operator (* in this case). Again, parentheses may be used to override priorities. For example, in

`(a + b) * c/d`

b is to be associated with the + operator.

In order to see how any infix expression is evaluated using priorities, and to develop an algorithm for this evaluation, consider the expression,

`a + (b * c/d ** e) *f  `

To evaluate it, when the first * is encountered the situation will be

`Operand Stack      Operator Stack`

`--------------------------------`

`     b                   (`

`     a                   +`

In this case, since the left parenthesis is on top of the operator stack, the * should be placed on top of the operator stack, and scanning continued. After c, division(/) is encountered and the stacks become

`Operand Stack      Operator Stack`

`---------------------------------`

`      c                  *`

`      b                  (`

`      a                  +`

At this point a decision must be made with respect to c: either it is to be associated with * (at the top of the stack) or with / (the current operator being processed). The standard rules associate c with the operator of highest priority. In this case, since * and / have equal priorities, associate c with the leftmost of the two operators in the input--that is, the top stack operator. Thus, the * must be popped, c and b must be popped, the * must be applied to b and c, and the result, (b * c), placed on top of the operand stack. Then the / must be placed on the operator stack. Had the current operator been of higher priority (say, **), then the current operator should simply be placed on the operator stack.

In the example, after / and d are processed, the stacks are as follows:

`Operand Stack      Operator Stack`

`---------------------------------`

`      d                  /`

`   (b * c)               (`

`      a                  +`

The ** becomes the current operator, and d must be associated with it or with /. Since ** has higher priority, place it on the operator stack; the result after processing e is

`Operand Stack      Operator Stack`

`---------------------------------`

`      e                  **`

`      d                  /`

`   (b * c)               (`

`      a                  +`

The current input character being scanned is now a right parenthesis. This "matches" the topmost left parenthesis on the stack. The next steps are to pop the operator stack; pop the operand stack to obtain the top two operands; apply **to them, and place the result back on the top of the operand stack. Then pop the operator stack; pop the operand stack to obtain the top two operands; apply / to them and place the result back on top of the operand stack; pop the stack again; and notice that a left parenthesis has appeared, signaling completion of the process for the current input character. The result is

` Operand Stack       Operator Stack`

`----------------------------------`

`((b * c)/(d ** e))         +`

`        a`

Finally, the last * is processed. It has higher priority than +, so it is placed on the operator stack. f is then processed and placed on the operand stack, yielding

` Operand Stack        Operator Stack`

`-----------------------------------`

`       f                    *`

`((b * c)/(d ** e))          +`

`       a`

Since the input is exhausted, the final steps are, for each remaining operator on the operator stack, to pop the operator stack, remove the required number of top operands from the operand stack, apply the operator, and place the result back on top of the operand stack. The final result appears at the top of the operand stack.

1. Initialize the operand stack to empty.

2. Initialize the operator stack to empty.

3. While there is another input character,

read the current character

if the current character is "(", then

push it on the operator stack;

else if the current character is an operand, then

push it on the operand stack;

else if the current character is an operator, then

if the operator stack is not empty, then

if the current character does not have greater priority than the top

operator stack character, then

pop the operator stack, remove the required number of operands

from the operand stack, apply the operator to them, and push the

result on the operand stack

push the current character onto the operator stack

else if the current character is ")", then

pop the operator stack and set topchar to the popped value

while topchar is not (

remove the number of operands required by topchar from the operand

stack, apply topchar to them, and

push the result onto the operand stack

pop the operator stack and set topchar to the popped value

4.While the operator stack is not empty,

pop the operator stack, remove the required number of operands from the

operand stack, apply the operator to them, and push the result on the operand

stack

5.Pop the operand stack and set evaluate to the popped value

## 4.6.3 Translating Infix to Postfix

The following modification of the infix evaluation algorithm results in such a translation.

1. Eliminate the operand stack. Instead, any pushing onto the operand stack should be changed to outputting the same value.

2. Instead of applying operators to operands, simply output the operators.

# 4.7: Queues

## 4.7.1 Array and Circular Array Implementation of the Queue

A queue may be implemented using an array of records by first declaring

`typedef struct`

`{`

`whatever info;`

`}queuerecord;`

`typedef struct`

`{`

`queuerecord queuearray [LIMIT];`

`int front, rear;`

`}queue;`

`queue q;`

As with stacks, overflow and underflow should be checked in a general implementation. A typical queue situation is depicted in Figure 4.10(a) for the array implementation. Figure 4.10(b) shows the situation after 18, 32, and 15 have been removed and 17 and 20 have been inserted.

Storage for insertion of more records is available at the top of the queuearray, but not at the bottom. To ensure that all the relocated storage for queue is used before overflow occurs, programs "wrap around." That is, the queue is implemented so that the queuearray is viewed as a circle of records, with 0 following the LIMIT, 7. Front is used to point to the entry at the front of the queue, and rear is used to point to the array location in which the next

#### Figure 4.10 Typical Queue Configuration for an Array Implementation

inserted record is to be placed. As entries are inserted, rear moves down until it "falls off" the array, then it must be "wrapped around." As entries are deleted, front moves down until it "falls off" the array, then it must "wrap around."

`insert(pnewrecord,pq)`

`/* Inserts newrecord at the rear of queue q */`

`queuerecord *pnewrecord;`

`queue *pq;`

`{`

`if ((*pq).front == -1)`

`{`

`(*pq).front = 0;`

`(*pq).queuearray[0].info = (*pnewrecord).info;`

`(*pq).rear = 1;`

`}`

`else`

`if((*pq).rear ==  (*pq).front)`

`printf("\n overflow \n");`

`else`

`{`

`if((*pq).rear <= (LIMIT - 1))`

`{`

`(*pq).queuearray[(*pq).rear].info =`

`(*pnewrecord).info;`

`(*pq).rear = (*pq).rear + 1;`

`}`

`else`

`{`

`if((*pq).front == 0)`

`printf("\n overflow \n");`

`else`

`{`

`4 there is room to wrap around, so the new entry is inserted at the start of the array and rear set to the next location`

`(*pq).queuearray[0].info =`

`(*pnewrecord).info;`

`(*pq).rear = 1;`

`}`

`}`

`}`

`}`

`remove (pq, pvalue)`

`/* Deletes the front entry from`

`queue q and copies its contents`

`into value`

`*/`

`queue *pq;`

`queuerecord *pvalue;`

`{`

`if(empty(pq))`

`printf("\n underflow \n");`

`else`

`{`

`(*pvalue).info = (*pq).queuearray`

`[(*pq).front].info;`

`(*pq).front = (*pq).front + 1;`

`if((*pq).front == (*pq).rear)`

`2 if queue is empty, then reinitialize it`

`setqueue(pq);`

`if((*pq).front > (LIMIT - 1))`

`(*pq).front = 0;`

`}`

`}`

## 4.7.3 List Implementation of the Queue with Records in Dynamic Memory

The third queue implementation is also a list--one involving dynamic storage allocation of the records in dynamic memory. First, the following declaration must be made:

`typedef struct record`

`{`

`whatever info;`

`struct record *link;`

`}queuerecord,*queue;`

Setqueue must set queue to null. Insert will first request storage for the new record to be inserted by invoking malloc. It will then set its info data and insert it as the new last record in the queue. Remove must delete the first record of the queue and return its info data.

Your deck has now been "stacked," you've been "queued" into queues, and you mustn't postpone your obligation to use them!

# 4.8: Case Study: Checking Sequences for Proper Nesting

1. The top-down approach

2. Demonstration of the use of the stack, treating it as a data abstraction

3. Checking program structure for proper nesting by developing a nonrecursive and a recursive function

4. The different perspectives required to develop the two functions

Every computer programmer has at one time or another gotten error messages saying "incomplete loop structure" or "a missing parenthesis." You now have enough background to write a program that checks for such errors. Let's see how it can be done.

Arithmetic expressions, as well as a program text, consist of sequences of symbols. Complex arithmetic expressions may be composed by properly combining simpler arithmetic expressions, delineated by matching left and right parentheses. The simpler expressions are said to be nested within the more complex expressions that contain them. The complex expression (a * (b + [c /d])) + b) contains two pairs of nested expressions. C programs contain compound statements delimited by matching { (begin) and } (end) pairs. Ignoring all other symbols, these matching pairs must satisfy rules of nesting to be syntactically correct.

Two abstractions of this problem will be considered. The second is a generalization of the first. To begin, assume only one kind of left parenthesis and one kind of matching right parenthesis, and consider sequences composed of these. Thus, at first, expressions such as ([]) are not allowed, since they involve more than one kind of parenthesis.

i. Each pair consists of a left and right parenthesis, with the left parenthesis preceding the right parenthesis.

ii. Each parenthesis occurs in exactly one pair.

Suppose you find that the resultant sequence is not valid. Can you conclude that the original sequence is not valid? In other words, has constraining one of the pairs to be the first adjacent "(" and ")" parentheses made a pairing of the original sequence satisfying (i) and (ii) impossible? The answer is no. To see this, assume that there is some valid pairing of the original sequence, in which the first ")" parenthesis is not paired with the immediately preceding "(" parenthesis, but there is no valid pairing in which it is. In general, the first ")" parenthesis must then be paired with an earlier "(" parenthesis, and the immediately preceding "("parenthesis must have been paired with a later ")" parenthesis, as in Figure 4.11(b). These two pairs can then be rearranged by interchanging their "(" parentheses. The resultant pairing satisfies conditions (i) and (ii), yet it has the first adjacent "(" parenthesis paired with the immediately following ")" parenthesis, but this is the nesting constraint that has been specified. This contradicts the assumption that no valid pairing satisfies the constraint.

Consequently, the conclusion is that a solution to the problem is obtained as follows:

1. Pair the first adjacent left, "(", and right, ")", parentheses and remove the pair.

2. If the resultant sequence is valid, then so is the original sequence; otherwise the original sequence is not valid.

Think of a left parenthesis as denoting an incurred obligation, and a right parenthesis as the fulfilling of the most recently incurred obligation. This is the precise situation for which a stack is useful. As the program scans a sequence

#### Figure 4.11 Valid and Invalid Nesting of Parentheses

from left to right, it pushes each "(" parenthesis onto a stack, representing an incurred obligation. Task 1 of the solution may then be carried out by popping the stack when the first ")" parenthesis is encountered, to fulfill the most recently incurred obligation.

Carrying out task 2 requires first determining if the resultant sequence is valid. Notice, however, that had the resultant sequence been processed in this same way, the contents of the stack would be exactly what they are now. Consequently, the program can continue to scan the original sequence (which is exactly what would be seen if it were scanning the resultant sequence), pushing whenever it encounters a "(" parenthesis, and popping whenever it comes to a ")" parenthesis. If the stack is empty when the entire scan is completed, then we have determined that the original sequence is valid; otherwise it is not. During the scan, any attempt to pop an empty stack means that no "(" parenthesis is available to be paired with the ")" parenthesis that caused the attempt (that is, the sequence is invalid).

Nonrecursive Version

`determine(pvalid)`

`/* Returns true in valid only if the`

`input sequence is properly nested`

`*/`

`int *pvalid;`

`{`

`char currentchar;`

`struct`

`{`

`char topchar;`

`}topcharacter;`

`stack s;`

`*pvalid = TRUE;`

`setstack(&s);`

`while(readchar(&currentchar))`

`if(leftparen(currentchar))`

`push(&currentchar,&s);`

`else if(rightparen(currentchar))`

`if(!empty(&s))`

`{`

`pop(&s,&topcharacter);`

`if(!match(topcharacter.topchar,`

`currentchar))`

`*pvalid = FALSE;`

`}`

`else`

`*pvalid = FALSE;`

`else`

`process(currentchar,&s);`

`if(!empty(&s))`

`*pvalid = FALSE;`

`}`

One of the aims of the text is to show how general functions can be adapted to solve particular problems. Determine is such a general function. It can be adapted to evaluate a completely parenthesized infix expression. We repeat the rule of Section 4.6.2 to be used to evaluate such an expression:

1. Scan the infix expression from left to right.

2. When a "matched" pair of "left" and "right" parentheses is encountered,

apply the operator to the operands enclosed within the pair of parentheses, and replace the paired parentheses and the contained operator and operands by the result. Continue scanning from this point.

The matched pairs referred to in this rule are exactly the same as in this case study. Studying the rule, you can see that a right parenthesis signals that an operator and its operands are enclosed between the right parenthesis and its matching left parenthesis.

1. When an operand is encountered, place the operand on top of an operand stack.

2. When an operator is encountered, place the operator on top of the operator stack.

It is also necessary, when a "right" parenthesis is encountered, and the operator stack is not empty, to pop the operator stack, remove the required number of operands from the top of the operand stack, apply the operator to those operands, and place the result on the top of the operand stack. This must be done just before the pop(&s,&topcharacter) statement. Determine's stack, s, plays the role of the operator stack. An operand stack must be introduced and must be available to both the evaluate and process functions.

Suppose, instead of containing only "(" and ")" parentheses, the input sequence could consist of any characters. Assume that each character could be either a left or a right character but not both, and also that each left character has a unique right character with which it matches. For instance, a, (, [, and 1 might be "left" characters and the unique "right" characters with which they match z, ), ], and r, respectively.

Given a sequence of left and right characters, determine if they may be paired so that

i. Each pair consists of a left and a right matching character, with the left character preceding the right character.

ii. Each character occurs in exactly one pair.

iii. The sequence of characters between the left and right characters of each pair must also satisfy (i) and (ii).

Let's see if this definition makes sense. Consider the above sample "matching" involving a, z, (, ), [, ], l, and r and the sequences of Figure 4.12.

Both the pairings of Figure 4.12(a) and those of Figure 4.12(b) satisfy (i) and (ii). However, only the pairing of (a) satisfies (iii). The pairing of (b) fails because the left and right characters of pair 3 are a and z, and the sequence of characters between them is ])1r. This sequence does not satisfy conditions (i), (ii), and (iii), because none of the six possible ways to form two pairs will be valid. It is also apparent that the pairing of (b) fails, because the left and right characters of pair 2 are "[" and "]" and the sequence of characters between them, a, is not valid. One would have to be sure no other pairings for (b) are valid before concluding that (b)is not a valid sequence.

It is not immediately apparent that this problem generalizes the first problem, even if the characters are restricted to be just left and right parentheses. This is because condition (iii) does not appear in the first problem. However, the reasoning used there shows that adding the condition does not change the problem. In fact, if the left and right matching characters are thought of as different kinds of parentheses, the same reasoning applied in the first problem can be applied to the present problem.

#### Figure 4.12 Valid and Invalid Nesting of Matched Characters

Again, any valid sequence must start with some series of n > 0 left parenthese preceding the first appearance of a right parenthesis. Suppose its matching left parenthesis does not immediately precede it. This is the situation, for example, in Figure 4.12(b), where there are four left parentheses, a, (, [, a, appearing before "]," the first right parenthesis. In order for this first right parenthesis to satisfy (i) and (ii), it must then be paired with a previous matching left parenthesis. But then the immediately preceding left parenthesis is the last character in the sequence between that pair of parentheses. In order to satisfy (iii), this sequence must be valid. This sequence cannot be valid since this last left parenthesis has no matching right parenthesis in this sequence, as indicated in Figure 4.13.

In conclusion, a solution may be obtained as follows:

1. Pair the first adjacent left and right parentheses that match, and remove the pair.

2. If the resultant sequence is valid, then so is the original sequence; otherwise the original sequence is not valid.

#### Figure 4.13 An Invalid Nesting Sequence

So far the solution has been nonrecursive and has required looking at the input as simply a sequence of parentheses satisfying certain local constraints; a left parenthesis must encounter a matching right parenthesis before any other right parenthesis appears. Any global structure inherent in the input has been ignored. Development of a recursive solution, however, requires that a valid input be defined recursively. The recursive definition of a valid sequence may be restated to show its structure more clearly.

A null sequence

A left and right matching pair of parentheses with a valid sequence between them

A valid sequence followed by a valid sequence

In other words, a valid sequence is

A null sequence,

One valid sequence surrounded by a pair of matching parentheses, or

A series of valid sequences, each surrounded by a pair of matching parentheses

The last case would appear as

(valid sequence)(valid sequence) . . . (valid sequence)

The following program is a recursive version of determine based on the recursive definition.

Recursive Version

`determine(pvalid,last)`

`/* Returns true in valid only if the input`

`sequence is properly nested; last must`

`initially contain a special character`

`used as the input terminator.`

`*/`

`int *pvalid;`

`char last;`

`{`

`char currentchar;`

`int done;`

`static int more;`

`done = FALSE;`

`more = TRUE;`

`while(!done && more)`

`17 loops through each input character`

`{`

`more = readchar(&currentchar);`

`if(leftparen(currentchar))`

`determine(pvalid,currentchar);`

`else if(rightparen(currentchar))`

`if(!match (last,currentchar))`

`*pvalid = FALSE;`

`else`

`{`

`done = TRUE;`

`last = SPECIALCHAR;`

`}`

`else`

`process(last,currentchar);`

`}`

`if(last != SPECIALCHAR)`

`*pvalid = FALSE;`

`}`

Both this recursive solution and the iterative solution work from the inside out. The iterative program looks for adjacent matching left and right parentheses in the interior of the sequence. The recursive program looks for a valid sequence surrounded by a matching pair of parentheses. Thus the iterative solution sees the input

`[ ( [ ] ) ] ( ) { [ ] } #`

as

`[ ( [ 1 ] ) ] ( 4 ) { [ 5 ] } #     (6 pairs of matching parentheses)`

`-   2   -    -   6   -`

`-  - 3   - -`

and the recursive solution sees it as

`[ ( [ ] ) ] ( 2 ) { [ ] } #    (3 valid sequences each one surrounded by a pair of`

`- -  1 - -         - 3  -       matching parentheses)`

where # denotes the specialchar.

Another recursive solution could be written to work from the outside in, looking for a rightmost mate to the first left parenthesis and then checking the sequence between them for validity. This would lead to a less efficient solution, because parentheses could be considered more than once. Recursion often involves this dual possibility, so both should be explored.

# Exercises

a. What is the value of q(7,2)?

b. Can we determine q(0,0)?

c. Can we determine q(-3, -4)?

m(a,i,n) is defined by

`m(a,i,n) = a[i] if i = n and max(m(a,i + 1,n) ,a[i]) if i < n`

a. Find m(a,i,n) if i = 1, n = 6, and a is

`0.   6.8`

`1.   3.2`

`2.  -5.0`

`3.  14.6`

`4.   7.8`

`5.   9.6`

`6.   3.2`

`7.   4.0`

b. What does m(a,i,n) do?

`(i + n)/2 means, "Do an integer divide of (i + n)/2."`

a. Find m(a,i,n) for i = 1, n = 6, and a the array of Exercise 2.

b. What does m(a,i,n) do?

`b(0) = 1`

`b(n) = b(0) X b(n - 1) + b(1) X b(n - 2)`

`+ b(2) X b(n - 3) + . . . + b(n - 1) X b(0) n>0`

b. What is the number of moves it uses?

1. Label the disks 1, 2, . . ., n in increasing order of size.

2. Label the pegs i, a, and , respectively, n + 1, n + 2, and n + 3.

3. Move the smallest disk onto another disk with an even label or onto an empty peg with an even label.

4. If all disks are on the same peg, then terminate. Move the second smallest top disk onto the peg not containing the smallest disk. Go to 1.

a. Convince yourself that this correctly solves the Towers of Hanoi problem.

b. Is the recursive solution or this nonrecursive version easier to understand.

a. Write a recursive solution for this problem.

b. Can you find a recursive solution that uses the minimum number of moves for this problem?

`(0) = 0, (1) = 1`

`(n) = f(n - 1) + (n - 2) for n = 2,3,4 . . .`

a. Write a recursive function fibonacci(n) to compute and print (n).

b. Analyze its time and storage requirements.

b. Analyze its time and storage requirements.

b. Same as Exercise 21(a), except assume you do have direct access to the stack.

24 What does the following do?

`pop(&s,&value);`

`push(&value,&s)`

`1 2 3 4 5 6 7 8`

`if ( ( ( ) ) ( ) ) is the input sequence,`

`then the output will be the pairs 3 4, 2 5, 6 7, 1 8.`

4 2 1 1 2 3 3 4

a. Develop an array-based implementation of a deque and write corresponding setdeque, insertf, insertr, removef, remover, and empty routines.

b. Do the same as in Exercise 41(a), except use pointer variables with dynamic storage allocation for the deque implementation.

# Suggested Assignments

1. Write and simulate a recursive program to reverse a list.

2. You might enjoy finding an algorithm for the following generalization of the Towers of Hanoi problem. The disks are each labelled with a positive integer. A configuration of disks on a peg is "legal" if each disk's integer is no larger than the sum of the integers on all disks below it, or there are no disks below it. How can the disks be moved so that any legal original configuration of n disks on peg 1 ends up on peg 3, with all intermediate configurations being legal?

3. Write the permutation program so it treats the permutation as a data abstraction.

4. In order to use storage efficiently when n stacks are needed during the execution of a program, it may be desirable to implement all the stacks in one array as shown here for n= 4.

The Bi's and Ti's point to the bottoms and tops of the stacks, which grow to the right as indicated. Think of the total storage currently allocated to stack i as being from B(i) to B(i + 1). Stack i is actually using T(i) - B(i + 1) + 1 positions of the array. If B1 = 1, B2 = 10, B3 = 15, B4 = 25, B5 = size of the array = 35, T1 = 3, T2 = 12, T3 = 20, and T4 = 33, then the stacks are using 3, 3, 6, and 9 entries, respectively, while they are allocated 9, 5, 10, and 10 entries.

When an entry is to be inserted into a stack that is currently using all its allocated storage, the stack is said to have overflowed. Stack i overflows if Ti = B(i + 1) - 1. Write a function to manage the storage provided by the array. Whenever a stack overflows, the function is to be invoked. If there is any unused space in the array, then the stack with an unused but allocated position which is "closest" to the overflow stack is to give up one of its unused positions. This position is then used by the overflow stack to accommodate its entry. This function must be written to shift stacks around. If no unused space exists in the array, then the procedure should print an "out of stack storage" message.