A recursive program, function, or procedure is one which invokes itself in processing the problem it is programmed to resolve. Recursive algorithms have the following characteristics :
The algorithm can be resolved to a simple case or cases with a trivial solution or solutions.
The more complex cases can be reduced to combinations of simpler cases of the same algorithm, and in the limit the simpler cases can be reduced to the trivial case or cases.
The simplest example of a problem which can be resolved using a recursive algorithm is calculating the factorial of a number. Factorial (n) is calculated as n * (n-1) * (n-2) * .... * 1, where factorial (1) is defined as 1. This problem can easily be implemented using iteration as follows :
program factorial_iteration;
var i, x : integer;
var ans : longint;
begin
ans := 1;
writeln ('Enter number to calculate factorial of ');
readln (x);
for i := 1 to x do
ans := ans * i;
writeln (ans);
end.
The only feature in this program which we have not used before is the definition of the variable ans as longint. Because the int datatype only holds values from -32768 to +32767, and because the upper limit of this range would be voilated calculating only factorial 8, we use a long integer data type to store the factorial calculation results.
To implement the factorial problem using recursion, we observe that :
factorial (n) = n * factorial (n-1) = n * (n-1) * factorial ((n-1) -1) and so forth until n-1 = 1.
We can write a factorial program which takes an argument n, and returns n multiplied by the factorial of (n-1) except in the trivial case where n = 1, when it returns 1. This implements the factorial problem, programmed above using iteration, using recursion :
program factorial_recursion;
var x : longint;
function fact (x : longint) : longint;
begin
if x = 1 then fact := 1
else fact := x * fact (x - 1)
end;
begin
writeln ('Enter number to calculate factorial of ');
readln (x);
writeln (fact(x));
end.
Here it can be seen that the function fact, which takes as a parameter and returns as a result a long integer type, invokes itself except until it reaches the trivial case where x = 1. The only practical aspect of this program, and other recursive programs, is the limit imposed by the computer memory available to continue to invoke the required recursive function, and the stack limit which the compiler may impose. This, in practise, may limit the number of times a recursive function can invoke itself.
The "Towers of Hanoii"
In the factorial example, there is no good reason to use a recursive program since the result can easily be achieved, taking up less memory, using iteration. However, there are some problems which are not easily solved using iteration and which are suited to a recursion solution. An example is the so called "Towers of Hanoi" problem.
In the "Towers of Hanoi", there are three pegs, A, B and C. On peg A there are a number of discs, 1 to n, 1 being the smallest and n being the biggest. The discs are impaled on peg A in decreasing order of size from bottom to top - disc n, the largest, is at the bottom through to disc 1, the smallest, at the top. The objective is to move all n discs from peg A to peg C (using, if required, the 'temporary peg', peg B) subject to the following constraints :
Only 1 disc, the top disc on any peg, can be moved at a time.
A larger disc cannot be placed on top of a smaller disc.
This problem, for n discs, can be defined recursively as follows :
IF n is 1, move disc 1 to the to peg from the from peg
ELSE
Move (n-1) discs to the temporary peg from the from peg using the to peg
Move disc n to the to peg from the from peg
Move (n-1) discs to the to peg from the temporary peg using the from peg
The code to achieve this is provided below, it is useful to trace through it and track its operation.
program towersofhanoi;
var n : integer;
var topeg, frompeg, temppeg : char;
procedure hanoi (frompeg : char; topeg : char; temppeg : char; n : integer);
begin
if (n = 1) then
writeln ('Move disc 1 from ',frompeg,' to ',topeg)
else begin
hanoi (frompeg, temppeg, topeg, n-1);
writeln ('Move disc ',n,' from ',frompeg,' to ',topeg);
hanoi (temppeg, topeg, frompeg, n-1);
end;
end;
begin
frompeg := 'A';
topeg := 'C';
temppeg := 'B';
writeln ('Towers of Hanoi problem');
writeln ('Enter number of discs on peg A initially ');
readln (n);
if (n < 1) then writeln ('Invalid number of discs')
else hanoi (frompeg, topeg, temppeg, n);
end.
Greatest Common Divisor
Another example of a problem which is suited to being written using recursion is Euclids solution to calculating the greatest common divisor (GCD) for two integers a and b. Euclids solution is defined as :
GCD (a,b) is GCD (b,a) if b < a
GCD (a,b) is a if a<=b and a divides into b giving an integer answer and no remainder.
else GCD (a,b) is GCD (b, modulus(b/a))
The code to calculate the GCD of two integers using this recursive algorithm is presented below :
program calculate_gcd;
var a, b, ans : longint;
function gcd (a : longint; b : longint) : longint;
begin
if ((a <=b) AND (0 = b mod a)) then gcd := a
else
if (b < a) then gcd := gcd (b, a)
else gcd := gcd (b, b div a);
end;
begin
writeln ('GCD calculator');
writeln ('Enter two numbers, separated by spaces, whose GCD you wish to calculate ');
readln (a, b);
if ((a < 1) or (b < 1)) then writeln ('Invalid parameters')
else ans := gcd (a,b);
writeln ('GCD of ',a,' and ',b,' is ',ans);
end.