HELP RECURSION                                          JLCunningham, July 1982

Anything that can be done using iteration (see HELP *LOOPS), can be done
instead using a programming technique called recursion. However, recursion is
a much more powerful technique, and some programs that can be written easily
using recursion would be difficult to write if restricted simply to iteration.

Briefly, in recursion a procedure does a task by splitting it into smaller
tasks, each of which is either like the original task but simpler or else is
simple enough to solve by other means.

The classical example is the 'Tower of Hanoi' problem.

-- THE TOWER OF HANOI --------------------------------------------------------

The problem is to move a stack of gold discs (each a different size) from one
cubit-long diamond needle to a second. But discs may only be released on a
diamond needle (there are three needles), only one disc may be moved at a
time, and a larger disc may never rest upon a smaller.

A recursive POP solution to this is as follows. The solution is printed by
calling HANOI, which takes four arguments: a number of disks to move, the
needle to move them from, the needle to move them to, and the remaining
needle).

    define hanoi(num_discs,needle_from,needle_to,needle_spare);
        if num_discs < 1 then
            ;;; there arent any discs so we don't have to do anything
            return
        endif;

        ;;; first move all but the bottom disc onto the spare needle
        ;;; to get them out of the way, (i.e. num_discs - 1 of them)

        hanoi(num_discs - 1, needle_from, needle_spare, needle_to);

        ;;; now move the bottom disc
        [move a disc from needle ^needle_from to needle ^needle_to]=>

        ;;; now move the other discs from the spare needle

        hanoi(num_discs - 1, needle_spare, needle_to, needle_from)
    enddefine;

An example call of this procedure is:

    hanoi( 3, "a", "b", "c")

to move 3 discs from needle "a" to needle "b" using needle "c".

This procedure (3 lines if you ignore the comments) sometimes seems like
magic to people who have programmed in languages like BASIC which don't
have recursion (it is very tricky to write non-recursively), and is
difficult to understand even for uncorrupted minds if they have not met
recursion before. It is worth making sure you understand it (try tracing it).
Don't try moving more than about 5 discs though.

For a tutorial introduction to recursion, see TEACH *RECURSE1 and
TEACH *RECURSE2.

See also HELP
    *LOOPS   - for types of iteration available in POP-11
    *CONTROL - for types of control structure available in POP-11
