Back

Recursion

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

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!

recurse

    • 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!

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

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.

Back