13.1 Problem Solving: The Nature of Recursion

Problems that lend themselves to a recursive solution have the following characteristics:

One or more simple cases of the problem (called stopping cases) have a simple, nonrecursive solution.
For the other cases, there is a process (using recursion) for substituting one or more reduced cases of the problem that are closer to a stopping case.
Eventually the problem can be reduced to stopping cases only, all of which are relatively easy to solve.

The recursive algorithms that we write will generally consist of an IF statement with the form shown below:

    IF the stopping case is reached THEN
    	Solve it
    ELSE
    	Reduce the problem using recursion
    END IF;

Figure 13.1 illustrates what we mean by this. Let's assume that for a particular problem of size N, we can split this problem into one involving a problem of size 1, which we can solve (a stopping case), and a problem of size N - 1, which we can split further. If we split the problem N times, we will end up with N problems of size 1, all of which we can solve.

Figure 13.1
Splitting a Problem into Smaller Problems

Figure 13.1

Example 13.1

Consider how we might solve the problem of multiplying 6 by 3, assuming that we know the addition tables but not the multiplication tables. The problem of multiplying 6 by 3 can be split into the two problems:

Problem 1. Multiply 6 by 2.

Problem 2. Add 6 to the result of problem 1.

Because we know the addition tables, we can solve problem 2 but not problem 1. However, problem 1 is simpler than the original problem. We can split it into the two problems 1.1 and 1.2, leaving us three problems to solve, two of which are additions.

Problem 1. Multiply 6 by 2.

Problem 1.1 Multiply 6 by 1.

Problem 1.2 Add 6 to the result.

Problem 2. Add 6 to the result of problem 1.

Even though we don't know the multiplication tables, we are familiar with the simple rule that, for any M, M × 1 is M. By solving problem 1.1 (the answer is 6) and problem 1.2, we get the solution to problem 1 (the answer is 12). Solving problem 2 gives us the final answer, 18.

Program 13.1 implements this approach to doing multiplication as the recursive Ada function Multiply, which returns the product, M x N, of its two arguments.

Program 13.1
Recursive Multiplication

FUNCTION Multiply (M : IN Integer; N : IN Positive) 
  RETURN Integer IS
-- Performs multiplication recursively using the + operator
-- Pre : M and N are defined and N > 0
-- Post: returns M * N           

  Result: Integer;
  
BEGIN  -- Multiply   

  IF N = 1 THEN
    Result := M;                     -- stopping case   
  ELSE
    Result := M + Multiply(M, N-1);  -- recursion   
  END  IF;

  RETURN Result;

END Multiply;

The stopping case is reached when the condition N = 1 is True. In this case, the answer is M (M x 1 is M). If N is greater than 1, the statement

    Result := M + Multiply(M, N-1) -- recursive step

executes, splitting the original problem into the two simpler problems:

Problem 1. Multiply M by N - 1.

Problem 2. Add M to the result.

The first of these problems is solved by calling Multiply again with N-1 as its second argument. If the new second argument is greater than 1, there will be additional calls to function Multiply. The recursive step in function Multiply splits the problem of multiplication by N into an addition problem and a problem of multiplication by N - 1.

To demonstrate how this function works, Program 13.2 shows Multiply modified to display the values of its parameters each time it is called, and the return value before it returns. The test program prompts the user for two numbers, then calls Multiply.

Program 13.2
A Test of Recursive Multiplication

WITH Ada.Text_IO;
WITH Ada.Integer_Text_IO;
PROCEDURE Test_Multiply IS
------------------------------------------------------------------------
--| Demonstration of recursive Multiply function
--| Author: Michael B. Feldman, The George Washington University 
--| Last Modified: July 1995                                     
------------------------------------------------------------------------

  FirstInt  : Integer;
  SecondInt : Positive;
  Answer    : Integer;

  FUNCTION Multiply (M : IN Integer; N : IN Positive) 
    RETURN Integer IS
  -- Performs multiplication recursively using the + operator
  -- Pre : M and N are defined and N > 0
  -- Post: returns M * N           

    Result: Integer;
    
  BEGIN  -- Multiply   

    Ada.Text_IO.Put(Item => "Multiply called with parameters ");
    Ada.Integer_Text_IO.Put(Item => M, Width => 1);
    Ada.Integer_Text_IO.Put(Item => N, Width => 1);
    Ada.Text_IO.New_Line;
    
    IF N = 1 THEN
      Result := M;                     -- stopping case   
    ELSE
      Result := M + Multiply(M, N-1);  -- recursion   
    END  IF;

    Ada.Text_IO.Put(Item => "Returning from Multiply with result ");
    Ada.Integer_Text_IO.Put(Item => Result, Width => 1);
    Ada.Text_IO.New_Line;

    RETURN Result;

  END Multiply;

BEGIN -- Test_Multiply

  Ada.Text_IO.Put(Item => "Please enter a integer > ");
  Ada.Integer_Text_IO.Get(Item => FirstInt);
  Ada.Text_IO.Put(Item => "Please enter a positive integer > ");
  Ada.Integer_Text_IO.Get(Item => SecondInt);

  Answer := Multiply(M => FirstInt, N => SecondInt);

  Ada.Text_IO.Put(Item => "The product of the two integers is ");
  Ada.Integer_Text_IO.Put(Item => Answer, Width => 1);
  Ada.Text_IO.New_Line;

END Test_Multiply;

Sample Run

Please enter a integer > 6
Please enter a positive integer > 3
Multiply called with parameters 6  3
Multiply called with parameters 6  2
Multiply called with parameters 6  1
Returning from Multiply with result 6
Returning from Multiply with result 12
Returning from Multiply with result 18
The product of the two integers is 18

Exercises for Section 13.1

Self-Check

Show the problems that are generated by the procedure call statement Multiply (5, 4). Use a diagram similar to Figure 13.1.