Introduction
Recursion is the term used to describe when a sub-program calls itself! After every call to itself a test is done. This checks to see if the sub-program should call itself again. This continues until the test result is such that the recursion (and therefore the calls to itself) ends. Recursion can require a little thought to fully understand the mechanism! Let's look at some examples. The first example is the classic factorial example using functions.

The 'factorial' of a number is arrived at by multiplying every integer from the number down to 1. So, for example,

Factorial(6) = 6 x 5 x 4 x 3 x 2 x 1 = 720
Factorial(4) = 4 x 3 x 2 x 1 = 24

Q1. What is a) Factorial(5) and b) Factorial(7)?

We can define a function that will work out the factorial of a number, K.

Function Fact(K)
BEGIN
IF K <=1 then
      Fact := 1
ELSE
      Fact := K x Fact(K-1)
END

A worked example
To see how this works, look at the following diagram and then read the description underneath. We want to find out the factorial of 3 so we call the function using the instruction Fact(3). Note that we have drawn a box around each call to the function. This helps us to remember the values of the variables. If you are working in a box then you use any variables’ values in that box!

• The function is called using Fact(3).

• K is set to 3 in this box.

• The test ‘K <= 1’ is FALSE. Therefore the 'ELSE' part of the selection construct is done.

• A variable called Fact in box 1 is set to K x Fact(K-1), or 3 x Fact(3-1).

• The Fact(3-1) part is a call to the function Fact using the parameter 3-1, or 2!

• We now jump to a new call to the function using Fact(2).

• K is set to 2 in this box.

• The test ‘K <= 1’ is FALSE. Therefore the 'ELSE' part of the selection construct is done.

• A variable called Fact in box 2 is set to K x Fact(K-1), or 2 x Fact(2-1).
  
  
• The Fact(2-1) part is a call to the function Fact using the parameter 2-1, or 1!
  
  
• We now jump to a new call to the function using Fact(1).
  
  
• K is set to 1 in this box.

• The test ‘K <= 1’ is TRUE. The IF part is executed and the variable Fact is set to 1.

• The call to box 3 ends and control is passed back to where the call was made from.

• Don't forget with functions, a value held in a variable whose name is the same as the function, is also passed back! So Fact:=1 is passed back and can replace the call that was made from box 2. In box 2, Fact is now set to 2 x 1 = 2.

• But box 2 has now finished. The value of Fact is passed back to replace where the call was made. So Fact:=2 is passed back to box 1.

• In box 1, Fact is set to 3 x 2 = 6. The answer to Fact(3) is therefore 6!

Q2. Using a diagram to support your answer, described how Fact(5) is calculated using the above function.

Another example
Study the next, totally meaningless procedure! If you can follow how this works, you have a good understanding of recursion that can only get better with experience!

The following procedure called Prog has been written. It accepts 3 values, an Integer and two strings. This recursion example doesn't use a function. It uses a procedure. In this case, values aren't passed back when a call has ended, although there are lots of outputs sent to the output screen.

Procedure Prog (n:Integer, S:String, T:String)
IF n=2 THEN
      OUTPUT S "I really love programming", T
ELSE
      Prog (n-2, T, S)
      OUTPUT "Hello", T
      Prog (n-2, S, T)
ENDIF

Q3. Draw a block diagram showing the calls and returns for Prog (6, Hello, Coops). Clearly show the output screen. The answer is at the back of the book.

As before, get into the habit of drawing a box around each call and identify the value of each of the variables within each box! It is also a good idea to show an output screen, so that you can display everything in the right order