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