First Textbook Examples of Recursion

We have shown how a factorial can be calculated by an iterative method (using a while loop). Program RecursionFactorial achieves the same result. It uses the equality 0! = 1 to provide the necessary stopping condition.

program RecursionFactorial;
  {$APPTYPE CONSOLE}
uses
  SysUtils;
var
  Num: integer;

function Factorial(i: integer): int64;
begin
  if i = 0 then
    result := 1
  else
    result := i * Factorial(i - 1);
end;

begin
  write('Please enter an integer from 0 to 20. ');
  readln(Num);
  writeln(Num,'! = ', Factorial(Num));
  readln;
end. 

Here is a dry run for the code when the entered Num = 3.

Factorial(3) becomes  3 * Factorial(2)
	Factorial(2) becomes 2 * Factorial(1)
		Factorial(1) becomes 1 * Factorial(0)
			Factorial(0) becomes 1 (Stopping condition, so the value 1 is returned ...)
		Factorial(1) evaluates to i * 1 = 1 * 1 = 1
	Factorial(2) evaluates to i * 1 = 2 * 1 = 2
Factorial(3) evaluates to i * 2 = 3 * 2 = 6  

There is no advantage to be gained by this particular recursive solution but you should be able to understand it before progressing to more complex examples.

The next programs compute Fibonacci numbers. In the Fibonacci sequence the first two terms are 1 and the rest are the sum of the previous two terms. This can be expressed as:

Fibonacci(i) = Fibonacci(i1) + Fibonacci(i2)     if i > 2
Fibonacci(i) = 1                                       if i = 2 or  i = 1

Dr Ron Knott's most impressive Fibonacci page illustrates the relevance of the sequence in nature. You should be able to understand Program Fibonacci1 easily, but you should be questioning the efficiency of the code.

program Fibonacci1;
  {$APPTYPE CONSOLE}
uses
  SysUtils;
var
  Num: cardinal;

function Fib(i: cardinal) : int64;
begin
  if (i = 0) or (i = 1) then
    result := 1
  else 
    result := Fib(i - 1) + Fib(i - 2);
end;

begin
  write('Please enter an integer 0 - 40 ');
  readln(Num);
  writeln('Fibonacci ', Num, ' = ', Fib(Num));
  readln;
end.  

The program, running on a newish PC, took 38 seconds to produce the result 1836311903 for the input of 45. The code is highly inefficient because it does not store values that it needs to reuse. Program Fibonacci2, based on Larry Birnbaum's efficient Python code, is more difficult to follow, but gives the same result instantly for Fibonacci 45. It contains nested functions.

program Fibonacci2;
  {$APPTYPE CONSOLE}
uses
  SysUtils;
var
  Num: cardinal;

function Fib(i: cardinal): int64;

function Fib2(n, p0, p1: cardinal): int64;
begin
  if n = 0  then
    result := p1
  else
    result := Fib2(n - 1, p1, p0 + p1);
end;

begin
  if i = 0 then
    result := 1
  else
    result := Fib2(i, 0, 1);
end;

begin
  write('Please enter an integer 0 - 46 ');
  readln(Num);
  writeln('Fibonacci ', Num, ' = ', Fib(Num));
  readln;
end.  

Experimenting with Recursion

  1. Write a recursive power function for integers.
  2. Write a program to calculate highest common factor of two integers using the Euclidean algorithm.

    The following suggestions are challenging, but there is plenty of help for each of them available in web pages.

  3. Write a program to solve the tower of Hanoi problem for the number of disks supplied by the user. (The representation of the disk positions should test your ingenuity).
  4. Write a program to output Pascal's triangle.
Programming - a skill for life!

First textbook examples of recursion, binary search trees and fractals