Section 3.8 introduced the idea of a sequence of numbers defined by a formula that could be applied to the numbers 1, 2, 3, 4, 5, ... in succession to produce the terms of the sequence. Not all sequences are defined in this manner; some are given in terms of a rule that works from previous terms to construct succeeding ones. For example, the *Fibonacci* sequence is defined as

a_{n} = 1 if n = 1 or 2

a_{n} = a_{n-1} + a_{n-2} otherwise.

Thus, the first few terms are: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Likewise, the mathematical function *factorial* is defined on non-negative integers as:

n! = 1 if n = 0

n! = n(n - 1)! if n > 0

Thus one has :

1! = 1 * 0! = 1 2! = 2 * 1! = 2 3! = 3 * 2! = 6 4! = 4 * 3! = 24 5! = 5 * 4! = 120 and so on.

Such definitions, and indeed any definition that uses itself as part of itself, is said to be *recursive*. Since Modula-2 procedures must be constructed to model the calculations they perform, they too may have occasion to use themselves.

Any routine that employs itself during execution is said to berecursive.

This idea will be introduced here with some simple examples. Much more sophisticated use will be applied later in the text in a variety of contexts.

For the first, consider a procedure that implements a computation of the factorial function as it is defined, that is, recursively.

PROCEDUREFac (num :CARDINAL) :CARDINAL;BEGINIFnum = 0THENRETURN1ELSERETURNnum * Fac (num - 1);END;ENDFac;

Suppose the flow of control in a program enters this procedure via the call *Fac (3)*. The statement under the ELSE would execute, causing 3 * Fac (2) to be computed. But this re-enters *Fac*, this time with *num* equal to 2. Since num is a *value* parameter, a new memory location is assigned to *num* on every entry. The statement under the ELSE executes again since num # 0, and a computation of 2 * Fac (1) is called for, so Fac is entered a third time asking for Fac (1). This causes a fourth entry to ask for Fac (0) which is dutifully returned back up the chain one step at a time. The successive returns are 1, 1, 2 and 6 and at the last return the calculation from the very first execution of ELSE concludes and the procedure ends.

There is one potential problem though. As in the writing of loops, one must be very careful not to specify a stopping condition on the chain of recursive calls that can never be achieved. (Here the stopping condition is n=0). Recursive procedures must be carefully designed, and not every programming language allows them, this being a technique that Modula-2 inherits from Pascal.

Even though the code given above does provide a simple and easily understood illustration of how recursion works, it is not difficult to see that calculating factorials does not have to be done recursively, for the solution is easily reformulated non-recursively as follows:

PROCEDUREFactorialNonRecursive (n :CARDINAL) :CARDINAL;VARcount, result :CARDINAL;BEGINresult := 1; count := 0;WHILEcount < nDOINC(count); result := result * countEND;RETURNresultENDFactorialNonRecursive;

On the other hand, recursion *is* inherent in a wide variety of problems, and some of these are rather more difficult to follow than the example above. In particular, it is not always so easy to reformulate a recursive idea in a non-recursive fashion. An ancient problem of intermediate difficulty whose solution is more naturally recursive is called the *Tower of Hanoi*. Often built as a child's toy, this puzzle consists of a rigid base into which are mounted three upright pegs, and a series of concentric disks of various sizes that can be placed over the pegs. To start with, all the disks are on one of the pegs, arranged with the largest at the bottom, in descending order of radius to the smallest at the top. The idea is to move all the disks from the first peg to the second, while at all times maintaining the correct size order on each of the pegs. That is, in making a move, one must always place a disk on top of one that is larger in diameter (not necessarily the next larger, but it must be larger).

This problem is best solved by building up a solution from the simplest case. Suppose that the three pegs are labelled *origin*, *destination*, and *temporary*. If there is only one disk involved in the game, then one need only to remove it from peg *origin* and place it on peg *destination* and the game is over.

If two disks are involved, the top one can be taken from *origin* and placed on *temporary*, and the game is then reduced to two single disk moves, namely of the second disk to *destination* and then the first one from *temporary* to *destination* on top of the larger disk.

If three disks are involved, one has to move two (one less than the total number) to the *temporary* peg (use the moves for a two-disk game as above), but using the *destination* peg as a *temporary*. Then one moves the bottom disk on the *origin* peg to the (now empty) *destination* peg and finally, using the *original* peg as a *temporary*, moves the two remaining ones to the final *destination*, again using a two-disk subgame. Likewise, if one starts with four disks, one first moves three to the *temporary* peg, using the *destination* peg as a *temporary* and the rules for a move of three disks (including the sub-games for two disks and one disk) then move the last disk to the *destination*, then again use the steps above for a game of three disks to transfer those disks now on the *temporary* peg to the *destination* peg using the origin peg as the *temporary*. That is, the game of four disks includes two sub-games of three disks, each with its sub-games of two disks and one disk.

That is, at any degree of complexity for the game, one can formulate the required steps to transfer a given number of pegs in terms of two sub-games involving one fewer disk, one before and one after a move of one disk. The overall solution is therefore formulated recursively in this fashion:

To move *numberToMove* disks from the origin peg to the destination peg:

- move
*numberToMove*- 1 disks to the temporary peg using the destination peg as a temporary - move the last disk to the destination
- move the
*numberToMove*- 1 disks again, this time to the destination, using the origin peg as the temporary

The procedure can call itself to do the moves, with the stopping point in each series of calls being the one at which only one disk needs to be moved. Each time the procedure is called, the pegs to be regarded as *origin*, *destination*, and *temporary* will depend on the current stage of the game.

This recursive procedure is formulated within a module that is capable of testing the entire operation and repeating the game several times. Assuming that the end user of the program has a physical model of the game onto which the moves can be translated as they are provided by the machine, instructions will be given as to which move to make at each step, with the top disk on a given peg always being the one being referred to.

MODULETryHanoi; (* Written by R.J. Sutcliffe *) (* to illustrate recursion *) (* using P1 Modula-2 for the Macintosh computer *) (* last revision 1993 02 26 *)FROMSTextIOIMPORTWriteString, WriteChar, WriteLn, ReadChar, SkipLine;FROMSWholeIOIMPORTReadCard, WriteCard;VARorigin, destination, temporary, key:CHAR; userNumber:CARDINAL;PROCEDURETowerOfHanoi (numToMove :CARDINAL; origin, destination, temp :CHAR);BEGINIFnumToMove = 1 (* only then do we move anything *)THENWriteString (" Move a disk from peg "); WriteChar (origin); WriteString (" to peg "); WriteChar (destination); WriteLnELSE(* else make a recursive call to this *) TowerOfHanoi ((numToMove - 1), origin, temp, destination); TowerOfHanoi (1, origin, destination, temp ); TowerOfHanoi ((numToMove - 1), temp, destination, origin )ENDENDTowerOfHanoi;BEGIN(* Main program starts here *) WriteLn; WriteString ('Before starting, please label the pegs of your '); WriteLn; WriteString ('Tower of Hanoi game as "A", "B", and "C".'); WriteLn; WriteString ('Now, place the disks in order on peg "A".'); WriteLn; WriteString ("Enter number of disks to move "); WriteString ("(use zero to end the program instead) ==>"); ReadCard (userNumber); SkipLine; WriteLn;IF(userNumber > 0)THENWriteLn; (* assume they start at "A" and end at "B" *) TowerOfHanoi (userNumber, "A", "B", "C")END; WriteString ("press any key to continue"); ReadChar (key);ENDTryHanoi.

One run of this program produced the following output in the selected file for the choice of four disks:

Before starting, please label the pegs of your Tower of Hanoi game as "A", "B", and "C". Now, place the disks in order on peg "A". Enter number of disks to move (use zero to end the program instead) ==>4 Move a disk from peg A to peg C Move a disk from peg A to peg B Move a disk from peg C to peg B Move a disk from peg A to peg C Move a disk from peg B to peg A Move a disk from peg B to peg C Move a disk from peg A to peg C Move a disk from peg A to peg B Move a disk from peg C to peg B Move a disk from peg C to peg A Move a disk from peg B to peg A Move a disk from peg C to peg B Move a disk from peg A to peg C Move a disk from peg A to peg B Move a disk from peg C to peg B press any key to continue

**NOTE**: An interesting addition to this would be an animation that shows the progress of the game as it is conducted, or perhaps one that scores a user's attempts to play the game by forbidding incorrect moves.

One more simple example of recursion is found in the next example. It differs from the last two in that the recursion is not of a procedure invoking itself directly, but of two procedures that cooperate on a task by invoking each other. The solution is presented in detail. The student who is unfamiliar with binary notation might wish to review section 8.2 for the theory.

Write and test a procedure that prints out cardinal numbers in binary form. It should be declared as: PROCEDURE WriteCardBin (card : CARDINAL).

This is the very kind of repeated computation that is especially suited to a computer solution. This type of conversion is based on repeated division, followed by writing down the remainders in reverse order. For instance, to convert 2456 to binary (base two) form, one divides by 2 repeatedly:

The binary equivalent of the decimal numeral is now read from the remainders in reverse order. It is 100110011000.

A solution to this problem can be formulated in terms of two procedures. The first will divide the remaining number by two and call the second to print the remainder. The second will examine the quotient and actually print the remainder if this quotient is zero. Otherwise, it will call the first procedure again before printing.

Only STextIO and SWholeIO are used. Procedures to obtain the number to convert, and to print cardinals (zero and one) are all that are required.

Two procedures that call each other present a little difficulty. Ordinarily, one follows a "declare-it-before-using-it" rule in Modula-2, at the very least for the sake of clarity and readability. The Modula-2 *language* rules do not require this be done, envisioning that the code can be scanned as many times as necessary to resolve these circular references. However, some Modula-2 compilers only scan the source code once, so they do have "declare-it-before-using-it" as an inflexible rule. The difficulty is, if two procedures call each other, which one ought to be written out first? This is solved in such versions by adding a special reserved word FORWARD following the declaration of the *syntax* of one of the procedures at a point before its code is produced. When this is done, the compiler can check that syntax in the invocation by the second procedure, and postpone looking for actual code. The body of the procedure can then be elaborated somewhere else in the program, as long as the parameter list is repeated exactly at the time that is done. Note that if the compiler is of the type that makes several passes through the code, it can resolve such references *without* needing to have one procedure declared as FORWARD.

If two procedures each invoke the other, or control can otherwise pass through a chain of procedure calls and reach the original calling procedure, this is calledmutual recursionorindirect recursion.

**NOTES**: 1. Although the multiple pass technique initially defined standard Modula-2, Wirth himself later began to write one-pass compilers in order to gain speed at compile time. As a result, FORWARD came to be regarded as an optional standard reserved word, rather than as a non-standard one. The ISO standard accepts this and allows compilers to conform regardless of which model is used, though multiple pass compilers should accept and deal correctly with FORWARD declarations, even if all they do is ignore them. That is, in the ISO standard, FORWARD is a reserved word; whether its use causes the compiler to do anything or not is optional.

2. The programmer must, as in all recursive situations, ensure that progress is actually made toward an eventual goal, or the program could end up executing in an infinite loop.

3. If the procedure being declared as FORWARD has a parameter list and/or a return type, this heading must be duplicated exactly when the procedure code is actually elaborated.

The only variables that are needed in the main program are a cardinal to convert, a character variable keyboard responses to questions, and a boolean for recycling the entire program. Necessary imports include ReadCard, WriteCard, WriteString, WriteLn, SkipLine, and ReadChar.

An input of 2456 will produce an output of 100110011000. No padding with blanks will be undertaken; the Write will take the amount of room necessary for the output number.

MODULECardBinConvert; (* Written by R.J. Sutcliffe *) (* to illustrate mutual recursion *) (* using P1 Modula-2 for the Macintosh computer *) (* last revision 1993 02 26 *) (* This program drives a procedure that prints a cardinal in binary form *)FROMSTextIOIMPORTWriteString, WriteLn, ReadChar, SkipLine;FROMSWholeIOIMPORTWriteCard, ReadCard; (*PROCEDUREWriteRem (whatsLeft, RemToPrint :CARDINAL);FORWARD; *) (* uncomment if one-pass version *) (* code comes later *)PROCEDUREWriteCardBin (x :CARDINAL); (* This procedure writes the supplied cardinal in binary form Pre: none Post: The binary representation is written to the standard output *)VARquotient, rem :CARDINAL;BEGINquotient := xDIV2; rem := xMOD2; WriteRem (quotient, rem);ENDWriteCardBin;PROCEDUREWriteRem (whatsLeft, remToPrint :CARDINAL); (* writes out the remainder from the division Pre: whatsLeft is the current quotient from dividing by two remToPrint is the last remainder obtained Post: if the quotient supplied was zero, the remainder is printed else, WriteCardBin is first called with the current quotient *)BEGINIFwhatsLeft > 0THENWriteCardBin (whatsLeft)END; WriteCard (remToPrint, 1); (* one digit, no space extra *)ENDWriteRem;VAR(* main program variables *) theNumber :CARDINAL; again :BOOLEAN; key, answer :CHAR;BEGINWriteString ("This program tests a procedure to print "); WriteString ("cardinals in binary form"); WriteLn;REPEAT(* main repeat loop *) (* get the number *) WriteString ("Enter the number to be changed "); WriteString ("to binary form ==> "); ReadCard (theNumber); SkipLine; WriteLn; WriteString ("The cardinal "); WriteCard (theNumber, 0); WriteString (" converted to binary form is: "); WriteCardBin (theNumber); WriteLn; WriteString ("Do another? Y/N "); ReadChar (answer); SkipLine; again := (CAP(answer) = "Y");UNTILNOTagain;ENDCardBinConvert.

Here is one run from this program:

This program tests a procedure to print cardinals in binary form Enter the number that is to be changed to binary form ==>12The cardinal 12 converted to binary form is: 1100 Do another? Y/NYEnter the number that is to be changed to binary form ==>15The cardinal 15 converted to binary form is: 1111 Do another? Y/NyEnter the number that is to be changed to binary form ==>65535The cardinal 65535 converted to binary form is: 1111111111111111 Do another? Y/NyEnter the number that is to be changed to binary form ==>0The cardinal 0 converted to binary form is: 0 Do another? Y/NyEnter the number that is to be changed to binary form ==>8The cardinal 8 converted to binary form is: 1000 Do another? Y/Nn