Patterns of recursion

A useful general template

We defined the command vprint as follows:

to vprint  :list
if empty?  :list [stop]
print first :list
vprint bf :list
end

This is clearly a recursive definition since vprint invokes vprint. But the structure of the body of the definition also exemplifies an overall pattern which appears in perhaps the majority of recursively defined procedures. The format is therefore useful as a template which can be adapted to many different circumstances:

  1. A check is made to see if some terminating condition is met. If so the recursion is halted.
    if empty? :list [stop]

  2. If the terminating condition is not met, some action is taken
    print first :list

  3. A recursive call is made using new input(s) based on a change to the current input variables
    vprint bf :list

Filling out a template

Becoming familiar with templates will help you to think up and develop your own recursive procedures more easily. But a template such as the one above is still a rather general one and it is, therefore, worth being aware of (and learning) some of the common variant forms it may take. These variations depend on:

As you will discover, the last two topics are in fact very closely related.



Ron Brasington
Department of Linguistic Science
The University of Reading
Reading
UK

E-mail: ron.brasington@rdg.ac.uk