AdaTutor - Recursion

Recursion

Ada procedures and functions may call themselves, directly or indirectly.  This process is called recursion.  While recursion often uses a little extra memory and execution time, for certain types of problems it pays large dividends in program simplicity.  That's a very worthwhile exchange!

For example, let's write a function to compute the factorial of a positive integer.  The factorial of an integer is the product of all the integers from that number down to one.  Thus, Factorial(5) = 5 * 4 * 3 * 2 * 1 = 120. Although we could easily write this function with a for loop, we'll use recursion instead.  Note that if N = 1, then Factorial(N) = 1; otherwise, Factorial(N) = N * Factorial(N - 1).

   function Factorial(N : in Positive) return Positive is
      Answer : Positive := 1;
   begin
      if N > 1 then
         Answer := N * Factorial(N - 1);
      end if;
      return Answer;
   end Factorial;

The highlighted line shows where this function calls itself.  Recursive subprograms always call themselves conditionally; otherwise the program would run out of memory, no matter how large the machine.  Here the recursive call is inside an if block.

Note that Answer is initialized to 1.  If the function is called with N = 1, the if statement is False, Answer isn't modified, and 1 is returned as the value of the function.  If the function is called with N = 2, the if statement is True, and the highlighted line is executed.  The machine starts to compute the expression as 2 * ..., and then Factorial is called with N = 1.  It's as if the machine made another copy of the code for Factorial and called that.  Actually there's only one copy of the code, but the machine maintains multiple pointers to it.

When the recursive call is made, the system allocates additional memory for new versions of any local variables like Answer.  Also, the parameters like N are separate for each recursive call.

Suppose the calling program calls Factorial with N = 2.  Then, in computing the expression, Factorial calls itself with N = 1.  In this second call, a new local variable Answer is created, separate from the one in the first call.  Also, parameter N is 1 in the second call, but 2 in the first call.  In the second call, the if statement is False, and 1 is returned.  In the first call, the calculation of the expression is completed, using the value 1 returned by the second call.  Thus, Answer becomes 2 * 1 = 2, and the first call returns the answer 2 to the calling program.

If the calling program calls Factorial with N = 3, the function starts to compute the expression as Answer := 3 * ..., and calls Factorial with N = 2.  In this second call, the function starts to compute Answer := 2 * ..., and calls Factorial with N = 1.  In this third call, the if statement is False, and the answer 1 is returned to the second call.  The second call finishes the computation of the expression Answer := 2 * 1, and returns the answer 2 to the first call.  Finally, the first call finishes computing the expression with Answer := 3 * 2, and returns the answer 6 to the calling program.

This simple function wouldn't have been complicated even without recursion.  In a moment we'll discuss the Tower of Hanoi problem.  The recursive solution is very simple, but a solution without recursion would be very complicated indeed.

Question

In this question, function A calls B, and B conditionally calls A. The specification of function B is given early so that A can call it.

   function B (I : in Integer) return Integer;

   function A (I : in Integer) return Integer is
   begin
      return B(I - 1) + 1;
   end A;

   function B (I : in Integer) return Integer is
      Ans : Integer := 0;
   begin
      if I > 0 then
         Ans := A(I);
      end if;
      return Ans;
   end B;

If the main program calls function A with a parameter equal to 2, what value will A return: 0, 1, 2, or 3? You may need pencil and paper to figure this one out.

0 - No, when the main program calls A(2), A starts to evaluate B(1) + 1.  The if statement in B is True, so B simply calls A(1).  The call A(1) starts to evaluate B(0) + 1.  The if statement in this call to B is False, so B(0) simply returns 0, and the call A(1) returns 0 + 1 = 1.  The call B(1) returns the same answer, so the call A(2) returns 1 + 1 = 2.

1 - No, when the main program calls A(2), A starts to evaluate B(1) + 1.  The if statement in B is True, so B simply calls A(1).  The call A(1) starts to evaluate B(0) + 1.  The if statement in this call to B is False, so B(0) simply returns 0, and the call A(1) returns 0 + 1 = 1.  The call B(1) returns the same answer, so the call A(2) returns 1 + 1 = 2.

2 - You're right!  When the main program calls A(2), A starts to evaluate B(1) + 1.  The if statement in B is True, so B simply calls A(1).  The call A(1) starts to evaluate B(0) + 1.  The if statement in this call to B is False, so B(0) simply returns 0, and the call A(1) returns 0 + 1 = 1.  The call B(1) returns the same answer, so the call A(2) returns 1 + 1 = 2.

3 - No, when the main program calls A(2), A starts to evaluate B(1) + 1.  The if statement in B is True, so B simply calls A(1).  The call A(1) starts to evaluate B(0) + 1.  The if statement in this call to B is False, so B(0) simply returns 0, and the call A(1) returns 0 + 1 = 1.  The call B(1) returns the same answer, so the call A(2) returns 1 + 1 = 2.

The Tower of Hanoi Problem

The "Tower of Hanoi" is a solitaire puzzle that was named when Hanoi was the capital of a free country: French Indochina.  There are three pegs labeled A, B, and C; one of them has a tower of N doughnut-shaped disks of decreasing size, like this:

          |                    |                    |
          |                    |                    |
         =|=                   |                    |
        ==|==                  |                    |
       ===|===                 |                    |
      ====|====                |                    |
     =====|=====               |                    |
  -----------------    -----------------    -----------------
          A                    B                    C

The object is to move the entire tower from one peg to another, say, from A to B.  Only one disk may be moved at a time, and a larger disk may never be placed on top of a smaller one.  The shortest solution to the puzzle with N disks requires 2**N - 1 moves.

For example, we can move five disks from A to B with the following 31 moves: (Read them from left to right, not in columns.)

A to B, A to C, B to C, A to B, C to A, C to B, A to B, A to C, B to C, B to A, C to A, B to C, A to B, A to C, B to C, A to B, C to A, C to B, A to B, C to A, B to C, B to A, C to A, C to B, A to B, A to C, B to C, A to B, C to A, C to B, A to B.

          |                    |                    |
          |                    |                    |
          |                    |                    |
          |                    |                    |
         =|=                   |                    |
      ====|====                |                    |
     =====|=====            ===|===               ==|==
  -----------------    -----------------    -----------------
          A                    B                    C
                    (The Puzzle After the First Five Moves)

Writing a program to display this series of moves would be very complicated without recursion.  Let's develop a recursive solution; we'll see that the resulting Ada program is surprisingly simple!

When we developed a recursive solution for the Factorial function:

          if N = 1,  Factorial(N) = 1
          otherwise, Factorial(N) = N * Factorial(N - 1)

we expressed Factorial(N) in terms of Factorial(N - 1), and gave the trivial solution for N = 1.  The Ada program was easily written from the above.

For the Tower of Hanoi problem, let's develop a solution for N disks in terms of a solution for N - 1 disks.  Suppose we want to move five disks from A to B, using C as a spare peg.  We first move four disks from A to C, then move one disk from A to B, and finally move four disks from C to B.  In general, to move N disks from a source peg to a destination peg, we first move N - 1 disks from the source to the spare, then move one disk from the source to the destination, and finally move N - 1 disks from the spare to the destination.

To move the one disk from the source to the destination, our program will simply display the move.  To move N - 1 disks, the program will call itself.  The solution for zero disks is trivial indeed: the program will do nothing!

The following program is extremely simple: three executable statements inside an if block.  Yet it can display a very complicated series of moves!

with Ada.Text_IO; use Ada.Text_IO;
procedure Hanoi(N : in Natural; From, To, Spare : in Character) is
begin
   if N > 0 then
      Hanoi(N - 1, From, Spare, To);
      Put_Line(From & " to " & To);
      Hanoi(N - 1, Spare, To, From);
   end if;
end Hanoi;

To move five disks from A to B, using C as a spare, we would call Hanoi(5, 'A', 'B', 'C'); and the program would display the 31 moves.

Note that when Hanoi is called with N = 0, it does nothing.  When called with N = 1, the if statement is true, and the three lines within the if block are executed.  But the first and third lines do nothing, because they call Hanoi with N = 0.  The second line displays, for example, A to B.

When called with a larger value of N, the first line within the if block moves N - 1 disks from the source to the spare peg.  The second line displays the move of one disk from the source to the destination, and the third line moves N - 1 disks from the spare peg to the destination.

Most implementations of Ada won't allow Hanoi to be a main program, because it has parameters.  A short main program to call Hanoi is shown here.  A slightly longer program could get N and the names of the three pegs from the user.  In this example, procedure Demo withs a previously compiled procedure rather than a previously compiled package.  We never write a use clause for a procedure or a function, because dot notation doesn't apply, as it does for packages.

with Hanoi;
procedure Demo is
begin
   Hanoi(5, 'A', 'B', 'C');
end Demo;

In summary, our first example of recursion, Factorial, was very simple.  However, that program would have been simple even without recursion.  Our second example, Hanoi, also was very simple, but the program would have been quite complicated without recursion.

Our fourth Outside Assignment will be to write a Fibonacci function Fib, using recursion.  As with Factorial, this function would be easy to write even without recursion.  However, as an exercise we'll write it using recursion.

< prev   next >