Home  Back Topics CD Orders  INDEX 
Recursion

Recursion provides elegant and simple solutions to complex problems with minimal coding.

A recursive algorithm...

  • calls itself inside its own definition.
  • must have a stopping condition which causes the algorithm to stop

Look at this example :

As the mathematicians will know, the factorial of an integer is the product of that integer and all the integers less than it. It is written n!.

So 5! = 5 x 4 x 3 x 2 x 1 = 120

The algorithm for working out the factorial of an integer n can be written down in pseudocode as follows -

Factorial(n : integer)

If n = 1 then
   factorial = 1
else
   factorial = n x factorial(n-1)
endif

This uses the fact that n! = n x (n-1)!

Note :

  • there is a stopping condition (if n = 1 then...)
  • the algorithm calls itself inside its own definition.

 
 

Another example

A routine which draws a line of n 'dashes' on a screen.

The normal iterative algorithm may look like -

DrawLineOfDashes(n : integer)

count := 0
repeat
  output('-');
  count := count + 1
until count = n

 Parameter n is the number of dashes.

-count the number of iterations.

The recursive method would look like -

DrawLineOfDashes(n : integer)

if n = 1 then
  output('-')
else
  output('-');
  DrawLineOfDashes(n-1)
endif

  

the terminating condition



the recursion