13.4 Problem Solving: More Recursive Programs

This section examines three familiar problems and implements a recursive procedure or function to solve each.

Case Study: Printing an Array Backward

PROBLEM SPECIFICATION

Provide a recursive solution to the problem of displaying the elements of an array in reverse order.

ANALYSIS

If the array X has elements with subscripts X'First..X'Last, the element values should be displayed in the sequence X(X'Last), X(X'Last-1), X(X'Last-2), ..., X(X'First+1), X(X'First). The stopping case is displaying an array with one element; the solution is to display that element. For larger arrays, the recursive step is to display the last array element (X(X'Last)) and then display the subarray with subscripts X'First..X'last-1 backward.

Data Requirements

Problem Inputs

an array of integer values (X : IntArray)

Problem Outputs

the array values in reverse order (X(X'Last), X(X'Last-1), ... , X(X'First+1), X(X'First))

DESIGN

Algorithm

1. IF X'First = X'Last (i.e., if slice X has only one element), THEN

2. Display X(X'Last)

ELSE

3. Display X(X'Last)

4. Display the subarray with subscripts X'First..X'Last-1

END IF;

IMPLEMENTATION

Program 13.7 implements the recursive algorithm and gives a test program.

Program 13.7
Printing an Array Backward

WITH Ada.Text_IO;
WITH Ada.Integer_Text_IO;
PROCEDURE Test_Print_Backward IS
------------------------------------------------------------------------
--| Demonstration of recursive procedure to print an array backward
--| Author: Michael B. Feldman, The George Washington University 
--| Last Modified: July 1995                                     
------------------------------------------------------------------------

  TYPE IntArray IS ARRAY(Integer RANGE <>) OF Integer;
  Test: IntArray(1..10);

  PROCEDURE PrintBackward (X : IntArray) IS
    
    -- Prints a slice of an integer array X with bounds X'First..X'Last.
    -- Pre : Array X is defined and X'First <= X'Last. 
    -- Post: Displays X(X'Last), X(X'Last-1), ... , X(X'First)
    
  BEGIN -- PrintBackward 

    IF X'First = X'Last THEN -- stopping case 
                             -- slice has only one element
      Ada.Integer_Text_IO.Put(Item => X(X'Last), Width => 3); 
    ELSIF X'First > X'Last THEN    -- error in specifying slice bounds
      Ada.Text_IO.Put(Item => "Error in bounds of array slice");  
      Ada.Text_IO.New_Line;
    ELSE
      -- recursive step   
      Ada.Integer_Text_IO.Put(Item => X(X'Last), Width => 3);
      PrintBackward (X => X(X'First..X'Last-1));
    END IF;

  END PrintBackward;

BEGIN -- Test_Print_Backward

  Test := (1,3,5,7,9,11,13,15,17,19);
  PrintBackward(X => Test(1..3));
  Ada.Text_IO.New_Line;

END Test_Print_Backward;

Sample Run

  5  3  1

Given the following array type and variable:

    TYPE IntArray IS ARRAY(Integer RANGE <>) OF Integer;
    Test: IntArray(1..3);

the procedure call PrintBackward(Test(1..3)) results in the three Put statements being executed in the order indicated below, and the elements of Test will be printed backward as desired.

    Ada.Integer_Text_IO.Put (Item => Test(3));
    Ada.Integer_Text_IO.Put (Item => Test(2));
    Ada.Integer_Text_IO.Put (Item => Test(1));

To verify this we trace the execution of the procedure call statement above in Figure 13.4.

Figure 13.4
Trace of PrintBackward(Test(1..3))

Figure 13.4

Each rightward arrow indicate a recursive procedure call; each leftward arrow indicates a return to the previous level.

Call PrintBackward with parameter Test(1..3).

Display Test(3).

Call PrintBackward with parameter Test(1..2).

Display Test(2).

Call PrintBackward with parameter Test(1..1).

Display Test(1).

Return from third call.

Return from second call.

Return from original call.

As shown, there are three calls to procedure PrintBackward, each with different parameters. The procedure returns always occur in the reverse order of the procedure calls; in other words, we return from the last call first, then we return from the next to last call, and so on. This time there are no statements left to execute after the returns, because the recursive call

    PrintBackward ( X( X'First..X'Last-1))

occurs at the end of the recursive step.

Case Study: Displaying an Array in Normal Order

PROBLEM SPECIFICATION

Provide a recursive procedure that displays the elements of an array in normal order.

ANALYSIS

We can use the approach just followed to display the elements of an array in normal order. Again the stopping case is an array with just one element.

Data Requirements

Problem Inputs

an array of integer values (X : IntArray)

Problem Outputs

the array values in normal order (X( X'First), X( X'First+1), ... , X( X'Last-1), X( X'Last))

DESIGN

Algorithm

1. IF X'First = X'Last (i.e., if slice X has only one element) THEN

2.Display X(X'Last)

ELSE

3. Display the subarray with subscripts X'First..X'Last-1

4. Display X(X'Last)

END IF;

The only difference between this algorithm and the one shown earlier is that steps 3 and 4 are transposed.

IMPLEMENTATION

The implementation and testing is left as an exercise.

You might be wondering if there are any special performance problems associated with passing arrays through a series of recursive calls. Recall that the Ada standard does not specify whether an array is passed to a subprogram by creating a local copy or by just passing its address. A compiler writer can choose to do it either way.

If indeed the array is passed by copying, hypothetically a large array might be copied many times in a recursive call, leading to a huge consumption of space for all the local copies and time for the copying. In practice, however, this is not a cause for concern because in most Ada compilers, if the array to be passed is longer than just a few elements, only its address is passed. Declaring an array parameter with mode IN (or unspecified mode) guarantees that it cannot be modified by the subprogram.

Case Study: Discovering Whether a String is a Palindrome

PROBLEM SPECIFICATION

A palindrome is a string or sentence that reads the same backward and forward. RADAR is a palindrome. When the Biblical first man met the Biblical first woman, he might have said "Madam, I'm Adam," which is a palindrome if one neglects the punctuation. (Adam, in his first fit of anger, might also have said "Mad am I, Madam.") The problem is to write a program that discovers whether a string of 80 characters or less is a palindrome.

ANALYSIS

Our program can discover whether a string is a palindrome by first finding the reverse of the string, then checking whether the string is the same as its reverse.

Data Requirements

Problem Inputs

the input string (S: String)

Problem Outputs

a message to the user indicating whether S is a palindrome.

DESIGN

Algorithm

1. Find the reverse R of the given string S

2. IF R is equal to S, THEN

the original string is a palindrome

ELSE

the original string is not a palindrome

END IF;

Step 1 Refinement

1.1. IF S is empty or has only one character, THEN

1.2. R is the same as S

ELSE

1.3. Remove the first character of S, and concatenate it to the reverse of the rest of S

END IF;

Step 1.3 contains the words "to the reverse of the rest of S." Because the purpose of the step is to find the reverse, this suggests a recursive algorithm. Step 1.1 tests for the stopping case; step 1.2 implements the stopping case. We can write this as a recursive code fragment:

    IF S'Length <= 1 THEN
      RETURN S;
    ELSE
      RETURN StringReverse(S(S'First+1..S'Last)) & S(S'First);;
    END IF;

The recursive call passes the tail of S, that is, S with the first character removed. We call our recursive function StringReverse and not Reverse because the latter is a reserved word in Ada, which we cannot use for anything else.

IMPLEMENTATION

Program 13.8 shows the program Palindrome, which uses the recursive function StringReverse just described. To make the output illustrate the recursion better, we have included an output statement in StringReverse that just displays the value of the parameter to this function. In the sample run you can observe that the string passed to StringReverse is shorter and shorter. Note also that we are using Get_Line to read the string, then passing only the useful slice to StringReverse.

Program 13.8
Palindrome

WITH Ada.Text_IO;
PROCEDURE Palindrome IS
------------------------------------------------------------------------
--| Display the reverse of a string of 80 characters or less, and
--| indicate whether the string is a palindrome
--| Author: Michael B. Feldman, The George Washington University 
--| Last Modified: July 1995                                     
------------------------------------------------------------------------

  Input: String(1..80);  -- the input string
  Last : Natural;        -- index of input string's last character
  R    : String(1..80);  -- the reverse of the input string


  -- local function StringReverse

  FUNCTION StringReverse(S: String) RETURN String IS
    -- returns the reverse of a string
    -- Pre: S is defined
    -- Post: returns the reverse of S

  BEGIN -- StringReverse

    -- these are just to illustrate the recursion
    Ada.Text_IO.Put(S);
    Ada.Text_IO.New_Line;

    IF S'Length <= 1 THEN
      RETURN S;
    ELSE
      RETURN StringReverse(S(S'First+1..S'Last)) & S(S'First);
    END IF;

  END StringReverse;

BEGIN -- Palindrome

  FOR Trial IN 1..5 LOOP

    Ada.Text_IO.Put
      (Item => "Please enter a string of 80 characters or less.");
    Ada.Text_IO.New_Line;
    Ada.Text_IO.Get_Line(Item => Input, Last => Last);

    R(1..Last) := StringReverse(Input(1..Last));
    Ada.Text_IO.Put("The reverse of the string is ");
    Ada.Text_IO.New_Line;
    Ada.Text_IO.Put(Item => R(1..Last));
    Ada.Text_IO.New_Line;

    IF R (1..Last) = Input (1..Last) THEN
      Ada.Text_IO.Put(Item => "The string is a palindrome.");
      Ada.Text_IO.New_Line;
    ELSE
      Ada.Text_IO.Put(Item => "The string is not a palindrome.");
      Ada.Text_IO.New_Line;
    END IF;

    Ada.Text_IO.New_Line;

  END LOOP;

END Palindrome;

Sample Run

Please enter a string of 80 characters or less.
radar
radar
adar
dar
ar
r
The reverse of the string is 
radar
The string is a palindrome.

Please enter a string of 80 characters or less.
Madam, I'm Adam
Madam, I'm Adam
adam, I'm Adam
dam, I'm Adam
am, I'm Adam
m, I'm Adam
, I'm Adam
 I'm Adam
I'm Adam
'm Adam
m Adam
 Adam
Adam
dam
am
m
The reverse of the string is 
madA m'I ,madaM
The string is not a palindrome.

Please enter a string of 80 characters or less.
madamimadam
madamimadam
adamimadam
damimadam
amimadam
mimadam
imadam
madam
adam
dam
am
m
The reverse of the string is 
madamimadam
The string is a palindrome.

Please enter a string of 80 characters or less.
abc
abc
bc
c
The reverse of the string is 
cba
The string is not a palindrome.

Please enter a string of 80 characters or less.
X
X
The reverse of the string is 
X
The string is a palindrome.

As you can see from the second and third test cases, this program treats blanks and punctuation marks as ordinary characters and so does not discover that "Madam, I'm Adam" is a palindrome. As an exercise, you can improve this program so that blanks and punctuation are ignored, and uppercase letters are treated the same as lowercase ones.

Exercises for Section 13.4

Self-Check

Trace the execution of PrintNormal and PrintBackward on an array that has the integers 5, 8, 10, 1 stored in consecutive elements.

Programming

Provide an iterative procedure that is equivalent to PrintBackward.
Write a recursive procedure that reverses the elements in an array X(1..N). The recursive step should shift the slice X(2..N) down one element into the subarray X(1..N-1) (i.e., X(1) gets X(2), X(2) gets X(3), ... X(N-1) gets X(N)), store the old X(1) in X(N), and then reverse the subarray X(1..N-1).