Recursion

After studying this section you should be able to use recursive techniques

Definition and application

Recursion is a very powerful technique that can be used when programming an algorithm in which there is a variable number of iterations. Recursive routines have two important features:

a recursive routine calls itself
it must have a terminating condition.

As a recursive routine calls itself there must be a way of stopping it or it will continue to call itself for ever in a continuous loop.

You will not normally be asked to write recursive algorithms but you may be asked to understand them.

An example is a procedure to produce a list of the square numbers. The procedure will be passed two parameters stating what the largest and smallest squares should be. This can be written non-recursively using a while loop as follows:

PROCEDURE Squares(Low, High)

     Count := Low

     WHILE Count <= High

          PRINT (Count * Count)

          Add 1 to Count

     ENDWHILE

ENDPROC

This could be written as a recursive procedure as follows:

PROCEDURE Squares(Low, High)

     IF Low <= High           /* Terminating condition */

          PRINT (Low * Low)

          Squares(Low+1,High)      /* recursive call */

     ENDIF

ENDPROC

Recursive routines have an if statement (not a while) to specify the terminating condition.

The recursive call asks that Squares be executed again with new parameters. The diagram below sets out how you might trace a call to Squares(1,3).

You can see from the trace table that Squares is called four times. After Squares is completed it returns to the statement following the recursive call (which is the ENDIF in this case). A useful hint is that lines of code that occur before the recursive call will be executed in the order of the calls, lines of code after the recursive call will be executed in reverse order.

Recursive calls are possible only if the system uses a stack to store the parameters and the return addresses.

Log in