Chapter Review

This chapter provides many examples of recursive procedures and functions. Studying them should give you some appreciation of the power of recursion as a problem-solving and programming tool and should provide you with valuable insight regarding its use. It may take some time to feel comfortable thinking in this new way about programming, but it is certainly worth the effort.

Quick-Check Exercises

Explain the use of a stack in recursion.
Which is generally more efficient (in terms of running time and space), recursion or iteration?
Which control statement do you always find in a recursive procedure or function?
Why would a programmer conceptualize the problem solution using recursion and implement it using iteration?
What causes a stack overflow error, indicated in Ada by Storage_Error?
What can you say about a recursive algorithm that has the following form?
```
IF condition THEN
  Perform recursive step
END IF;
```

Answers to Quick-Check Exercises

The stack is used to hold all parameter and local variable values and the return point for each execution of a recursive procedure.
Iteration is generally more efficient than recursion.
IF statement.
When its solution is much easier to conceptualize using recursion but its implementation would be too inefficient.
Too many recursive calls.
Nothing is done when the stopping case is reached.

Review Questions for Chapter 13

Explain the nature of a recursive problem.
Discuss the efficiency of recursive procedures.
Differentiate between stopping cases and a terminating condition.

Convert the program below from an iterative process to a recursive function that calculates an approximatevalue for e, the base of the natural logarithms, by summing the series

1 + 1/1!+ 1/2!+ ...+1/N!

until additional terms do not affect the approximation.

PROCEDURE ELog IS

  ENL:   Float;
  Delta: Float;
  Fact:  Float;
  N:     Float;

BEGIN -- Elog

  ENL := 1.0;
  N := 1.0;
  Fact := 1.0;
  Delta := 1.0;

  LOOP
    ENL := ENL + Delta;
    N := N + 1.0;
    Fact := Fact * N;
    Delta := 1.0 / Fact;
  EXIT WHEN ENL = (ENL + Delta);

  Ada.Text_IO.Put(Item => "The value of e is ");
  My_Flt_IO.Put(Item => ENL, Fore => 3, Aft => 15, Exp => 0);

END Elog;

Programming Projects

Write a procedure that reads each row of an array as a string and converts it to a row of Grid (see Fig. 13.9). The first character of row 1 corresponds to Grid(1,1), the second character to Grid(1,2), and so on. Set the element value to Empty if the character is blank; otherwise, set it to Filled. The number of rows in the array should be read first. Use this procedure in a program that reads in cell coordinates and prints the number of cells in the blob containing each coordinate pair.
The expression for computing C(n, r), the number of combinations of n items, taken r at a time,is
```
               n!
C(n, r) = -----------
           r!(n - r)!
```
Write and test a function for computing C(n, r) given that n! is the factorial of n.
Write a recursive function that returns the value of the following recursive definition:
F(X, Y) = X - Y if X or Y < 0
F(X, Y) = F(X - 1, Y) + F(X, Y - 1) otherwise
Write a recursive procedure that lists all of the pairs of subsets for a given set of letters.For example:
('A', 'C', 'E', 'G') => ('A', 'C'), ('A', 'E'), ('A', 'G'), ('C', 'E'), ('C', 'G'), ('E', 'G')
Write a procedure that accepts an 8 x 8 array of characters that represents a maze. Each position can contain either an 'X' or a blank. Starting at position (1, 1), list any path through the maze to get to location (8, 8). Only horizontal and vertical moves are allowed (no diagonal moves). If no path exists, write a message indicating this. Moves can be made only to locations that contain a blank. If an 'X' is encountered, that path is blocked and another must be chosen. Use recursion.
One method of solving a continuous numerical function for a root implements a technique called the bisection method, which is similar to the binary search. Given a numerical function, defined as f(X), and two values of X that are known to bracket one of the roots, an approximation to this root can be determined through a method of repeated division of this bracket.
For a set of values of X to bracket a root the value of the function for one X must be negative and the other must be positive. This is illustrated in Figure 13.12, which plots f(X) for values of X between X1 and X2.
Figure 13.12
Diagram for Bisection Method

The algorithm requires that the midpoint between the left X and the right X be evaluated in the function. If the midpoint equals zero, the root is found; otherwise, the left X (X1) or right X (X2) is set to this midpoint. To determine whether to replace either X1 or X2, the sign of the midpoint is compared against the signs of the values of f(X1) and f(X2). The midpoint replaces the X (X1 or X2) whose function value has the same sign as the function value at the midpoint.
This routine can be written recursively. The terminating conditions are true when either the midpoint evaluated in the function is zero or the absolute value of the left minus the right X is less than some small predetermined value (e.g., 0.0005). If the second condition occurs, the root is said to be approximately equal to the midpoint of the last set of left and right Xs.
We can use a merge technique to sort two arrays. The mergesort begins by taking adjacent pairs of array values and ordering the values in each pair. It then forms groups of four elements by merging adjacent pairs (first pair with second pair, third pair with fourth pair, and so on) into another array. It then takes adjacent groups of four elements from this new array and merges them back into the original array as groups of eight, and so on The process terminates when a single group is formed that has the same number of elements as the array. Figure 13.13 shows a mergesort for an array with eight elements. Write a MergeSort procedure.
Figure 13.13
Merge Sort
Improve the palindrome-finding program (Program 13.8) so that blanks and punctuation are ignored and the program is case-insensitive. (Hint: Use operations from Ada.Characters.Handling to write a function which takes a string S as a parameter and returns a string representing S with all letters converted to uppercase, as well as blanks and punctuation removed. "Madam, I'm Adam" would be converted to "MADAMIMADAM". Use the result of calling this function as the input to StringReverse.)
Modify BinarySearch into a procedure with two output parameters: the location of the key if found and a flag indicating whether or not the key was found.
Using the modified BinarySearch of Programming Project 9 as a starting point, write a generic binary search procedure that can handle any array with any nonlimited element type and any index type.