#### 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 thenAnswer := 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.

#### 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 **with**s 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.

## No comments:

Post a Comment