perm filename RECUR.PUB[2,TES] blob sn#038071 filedate 1973-04-25 generic text, type T, neo UTF8

00050 .TURN ON "#∪↓_" 00100 .PAGE FRAME 61 HIGH 80 WIDE; 00150 .TEXT AREA TEXT LINES 1 TO 60 CHARS 1 TO 80; 00200 .TITLE AREA FOOTING LINE 61; 00250 .PLACE TEXT; 00300 .COUNT PAGE FROM 1 TO 999; EVERY FOOTING(,{PAGE},); 00350 .MACRO ASIS ⊂ BEGIN NOJUST NOFILL ⊃ 00400 .MACRO FIG(N) ⊂ SKIP N ⊃ 00450 .MACRO SK(N) ⊂ SKIP N ⊃ 00500 .BEGIN FILL ADJUST INDENT 0,0 00550 .ASIS 00600 ↓_RECURSION_↓ 00650 .END 00700 .SK 4 00750 These notes introduce a programming technique called 00800 ↓_recursion_↓. This technique does not require any new 00850 ALGOL W commands, but rather uses the facilities we have 00900 already introduced, particularly procedures, in a new way. 00950 We shall illustrate the recursion technique with 01000 a number of examples; these range from cases where recursion 01050 seems a needlessly difficult method of solving the problem 01100 to cases where it is a very natural method. 01150 01200 ↓_Example 1: Counting Marbles_↓ 01250 01300 Suppose you have two bags full of marbles: 01350 a red bag full of red marbles and a green bag full of 01400 green marbles. You wish to answer the question: are there (a) 01450 more red marbles than green marbles, (b) more greens than reds, 01500 or (c) equal numbers of marbles. 01550 01600 ↓_Method 1.0:_↓ The simplest technique would be to count the number 01650 of red marbles (say R) and the number of green marbles (say G), 01700 Then our answers are: 01750 .ASIS 01800 01850 (a) if R > G 01900 (b) if G > R 01950 (c) if G = R 02000 02050 .END 02100 However, this method is very inefficient in certain cases. 02150 Suppose we counted and found R = 10 and G = 150000. 02200 Clearly, we have expended a lot of effort in counting the green 02250 marbles, although the effort required to answer the 02300 question is much less. 02350 02400 ↓_Method 1.1:_↓ To avoid the inefficiency, we could proceed 02450 as follows: 02500 .SK 1 02550 .BEGIN INDENT 6,3 02600 1.#If the red bad and green bag are both empty, announce 02650 that the answer is (c). If not, go to step 2. 02700 02750 2.#If the red bag is empty, then the answer is (b). Otherwise 02800 proceed: 02850 02900 3.#If the green bag is empty, then the answer is (a). Otherwise, 02950 go to step 4. 03000 03050 4.#If we come to this step, neither bag is empty. Remove 03100 one marble from the red bag and one from the 03150 green bag. Then go to step 1. 03200 .END 03250 .SK 1 03300 This procedure only "counts" (step 4) enough marbles to solve 03350 the problem. Furthermore, notice that we never really process 03400 ↓_numerical_↓ quantities R or G; thus the technique 03450 can be extended to non-numerical processes (**** comparing strings?). 03500 03550 We can express steps 1 to 4 in an ALGOL W notation as follows: 03600 .ASIS 03650 03700 WHILE green_bag_not_empty AND red_bag_not_empty DO 03750 BEGIN 03800 remove_marble_from_red_bag; 03850 remove_marble_from_green_bag 03900 END; 03950 IF green_bag_not_empty THEN answer_is_b ELSE 04000 IF red_bag_not_empty THEN answer_is_a ELSE 04050 answer_is_c ; 04100 04150 .END 04200 (Note: the expressions in lower case above are not legal 04250 ALGOL W constructs; they merely suggest what must be filled 04300 in.) This method is called an "iterative solution" because 04350 an indefinite iterative loop is used to construct the program. 04400 04450 ↓_Method 1.2:_↓ This problem can also be solved with the recursion 04500 technique. We shall initially illustrate the method 04550 with a rather inane "story." Suppose that Tom is the owner of the 04600 bags and has an inexhaustible supply of friends (Huck, Becky, etc.). 04650 We shall simplify our notation for Tom and friends 04700 to PERSON0 (Tom), PERSON1, PERSON2, etc. Tom's last name is 04750 (predictably) Sawyer, and he conceives an ingenious plan for 04800 answering the bags question without his doing any work. 04850 He will give each friend the following instructions: 04900 .SK 1 04950 .BEGIN INDENT 6,3 05000 1.#When you are handed two bags by someone, inspect them carefully 05050 and perform the following steps. 05100 05150 2.#If both bags are empty, tell the person who handed the bags 05200 to you that the answer is "c". Then you are finished, and can go 05250 to the picnic, get lost in the cave, etc. 05300 05350 3.#If the red bag is empty, tell the person who handed 05400 it to you that the answer is "b" and go play. 05450 05500 4.#If the green bag is empty, tell the person who 05550 handed it to you that the answer is "a" and go play. 05600 05650 5.#If steps 2-4 didn't apply, you can't go play quite yet. 05700 Remove one marble from each bag. Then find a free (as yet unused) 05750 person and give both bags to him/her. Now wait until that 05800 person tells you the "answer" (this will certainly happen). 05850 Then repeat this answer to the person who originally handed the 05900 bags to you. Now go play. 05950 .END 06000 .SK 1 06050 Tom (PERSON0) starts the process by giving the bags to PERSON1. 06100 If necessary, he/she passes them to PERSON2 in the course of 06150 executing the above instructions, etc. 06200 06250 Let us show diagramatically the process for G = 4, R = 3. 06300 06350 .SK 2 06400 .BEGIN INDENT 30,30 06450 Tom (PERSON0) hands the bags to PERSON1 and waits for an answer. 06500 PERSON1 discovers that none of steps 2-4 apply, and removes a marble 06550 frommeach bag (step 5) and hands them to PERSON2. 06600 .SK 3 06650 PERSON2 likewise discovers that steps 2-4 aren't true, removes a 06700 marble from each bag, and hands off to PERSON3, and awaits PERSON3's 06750 answer. 06800 .SK 3 06850 And to PERSON4. 06900 .SK 4 06950 Now PERSON4 discovers that the red bag is empty, so 07000 he/she is instructed to tell PERSON3 that the answer is "b" and 07050 then go ply (step 3). 07100 .SK 4 07150 Then PERSON3 is instructed (by step 5) to repeat the answer to 07200 PERSON2 and go play. 07250 .SK 4 07300 and so forth until PERSON1 tells our hero that the 07350 answer is "b". 07400 .SK 4 07450 .END 07500 This process has consumed quite a quantity 07550 of resources (friends) and has seemed needlessly complicated. 07600 It might have been more natural for Tom to sit down with his 07650 bags and use method 1.1 to arrive at an answer. However, we 07700 shall see below that some problems are ↓_easier_↓ to formulate 07750 with recursion (method 1.2) than iteration (method 1.1). 07800 07850 We shall not carry this example furhter, or try to write an 07900 ALGOL W program that mimics the recursive solution of this ppoblem. 07950 However, we shall make the following characterization of a 08000 recursive solution: 08050 .SK 1 08100 .BEGIN INDENT 6,3 08150 1.#Apply some tests to see if the problem is so trivial that 08200 it can be solved directly. Steps 2-4 of the example are such tests. 08250 08300 2.#If the solution is not trivial, express the solution of the 08350 problem in terms of the solution of a slightly simpler problem 08400 (e.g. the problem of answering the question for bags with 08450 one fewer marble in each one). Then find a new PERSON to solve the 08500 slightly simpler problem. When he/she returns an answer, 08550 you can then formulate the answer to the original problem 08600 (in the example above, the answer to the original problem is 08650 the same as the answer to the simpler problem -- hence we 08700 merely repeat the answer). 08750 .SK 2 08800 .END 08850 ↓_Example 2: The Factorial Function_↓ 08900 08950 We shall now illustrate the iterative and recursive formulations 09000 of a specific computational problem: computing the factorial 09050 of a number. We can express the factorial of a number, n, as follows: 09100 .ASIS 09150 09200 factorial(n) = n * (n-1) * (n-2) * ... * 2 * 1 09250 factorial(0) = 1 09300 09350 .END 09400 Notice that factorial is not defined for n < 0. This formulation 09450 immediately suggests an iterative solution. 09500 09550 ↓_Method 2.1:_↓ Iterative Solution to Factorial 09600 09650 The special case of factorial(0) can be removed by rewriting 09700 the definition slightly (multiplying any expression by 1 leaves 09750 its value unchanged): 09800 .ASIS 09850 09900 factorial(n) = 1 * 1 * 2 * ... * (n-2) * (n-1) * n 09950 10000 n terms in all 10050 10100 .END 10150 Thus, for n = 0, we have zero terms following the initial 10200 "1", and factorial(0) = 1. Here is an ALGOL W procedure that 10250 computes factorial: 10300 .ASIS 10350 10400 INTEGER PROCEDURE FACTORIAL (INTEGER VALUE N); 10450 BEGIN INTEGER M; 10500 M := 1; 10550 FOR I := 1 UNTIL N DO 10600 M := M * I ; 10650 M 10700 END; 10750 10800 .END 10850 You may wish to "hand compute" several values of factorial 10900 using this technique to see that it is correct. 10950 A brief table of factorials is: 11000 .ASIS 11050 11100 n factorial(n) 11150 0 1 11200 1 1 11250 2 2 11300 3 6 11350 4 24 11400 5 120 11450 6 720 11500 11550 .END 11600 .SK 2 11650 ↓_Method 2.2:_↓ Recursive Solution to Factorial 11700 11750 Let us try to formulate the factorial problem in the recursive 11800 paradigm described above: 11850 .SK 1 11900 .BEGIN INDENT 6,3 11950 1.#If the problem is trivially solvable, compute the answer. 12000 12050 2.#Otherwise, use the same procedure to answer a 12100 simpler problem, and then compute the answer to the original 12150 problem based on this answer. 12200 .SK 1 12250 .END 12300 Writing the definition of factorial again: 12350 .ASIS 12400 12450 factorial(n) = n * (n-1) * (n-2) * ... * 2 * 1 12500 12550 .END 12600 We see that the epxression on the right can be broken into two parts: 12650 n (the first term) and all remaining terms: 12700 .ASIS 12750 12800 factorial(n) = [n] * [(n-1)*(n-2)* ... *2*1] 12850 12900 .END 12950 The second quantity inside square brackets is just exactly 13000 the expression for factorial(n-1), which we obtain by substituting 13050 n-1 for n in the original definition: 13100 .ASIS 13150 13200 factorial(n-1) = (n-1) * (n-2) * (n-3 ) * ... * 2 * 1 13250 13300 .END 13350 Hence we have: 13400 .ASIS 13450 13500 factorial(n) = n * factorial(n-1) 13550 13600 .END 13650 Buth this is not quite correct for our special case of n = 0. 13700 We know that factorial(0) = 1, but the above definition would have 13750 it be 13800 .ASIS 13850 13900 factorial(0) = 0 * factorial(-1) 13950 14000 .END 14050 which is probably not 1 (remember that factorial is not 14100 even defined for negative numbers!). So we must alter our definition 14150 to include the special case: 14200 .ASIS 14250 14300 factorial(n) ↓_is_↓ 14350 if n=0 then the answer is 1 14400 otherwise the answer is n * factorial(n-1) 14450 14500 .END 14550 This definition now matches exactly the recursive 14600 paradigm! The "trivial problem" that we know the answer to 14650 is factorial(0). In all other cases, if we can compute 14700 the answer to a slightly simpler problem (factorial(n-1)) 14750 we can compute the answer to the original problem (factorial(n)). 14800 14850 We can not compose the instructions for our stick-figure 14900 computing persons: 14950 .SK 1 15000 .BEGIN INDENT 6,3 15050 1.#If you are asked to compute the factorial of a number, say n, 15100 do he following steps: 15150 15200 2.#If n is zero, tell the person who asked you to compute factorial 15250 that the answer is "1"; then go play. 15300 15350 3.#Otherwise, find an unoccupied person, and ask him/her to compute 15400 the factorial of n-1. Wait for an answer. When it arrives, multiply it 15450 by n (note that this requires you to remember the value of n) and 15500 then give this answer to the person who originally asked you to 15550 compute the factorial of n. Then go play. 15600 .SK 1 15650 .END 15700 We shall draw a few stages in the computation of factorial(3). 15750 .FIG 5 15800 PERSON3 is shown giving the problem "factorial(0)" to 15850 PERSON4. Note that PERSONs 1, 2 and 3 are "remembering" their 15900 values of n while awaiting answers. Now PERSON4, by step 2, 15950 returns an answer of "1" to PERSON3. PERSON3 computes 16000 n*1 = 1*1 = 1, and gives that answer to PERSON2, who computes 16050 n*1 = 2*1 = 2 and gives that answer to PERSON1, who 16100 computes n*2 = 3*2 = 6, and gives that answer to PERSON0 16150 (Tom Sawyer). 16200 16250 Let us now write an ALGOL W ↓_procedure_↓ that mimics the 16300 functions of PERSON1 above: 16350 .ASIS 16400 16450 INTEGER PROCEDURE PERSON1 (INTEGER VALUE N); 16500 BEGIN INTEGER ANSWER; 16550 COMMENT PERSON1 is "called" in order to compute the factorial of N. 16600 He allocates a variable ANSWER to hold his answer.; 16650 IF N=0 THEN ANSWER := 1 16700 COMMENT The above test implements step 2 of the instructions 16750 outlined above. However, PERSON1 just records the answer. Later, 16800 he/she will pass it back to the person who called PERSON1.; 16850 ELSE ANSWER := N * PERSON2(N-1) ; 16900 COMMENT This step computes the value of N-1, and calls upon PERSON2 16950 to compute the answer to factorial(n-1). When that answer is 17000 computed and returned by PERSON2 (PERSON2 will be an 17050 integer procedure), then PERSON1's answer is computed by 17100 multiplying by N.; 17150 ANSWER 17200 COMMENT Now return the ANSWER to the person who asked for it 17250 (i.e. who called PERSON1).; 17300 END; 17350 17400 .END 17450 We can shorten the procedure by removing the comments 17500 and using a conditional expression to compute the answer: 17550 .ASIS 17600 17650 INTEGER PROCEDURE PERSON1 (INTEGER VALUE N); 17700 IF N=0 THEN 1 ELSE N*PERSON2(N-1); 17750 17800 .END 17850 Now, of course, we must write a procedure for PERSON2. The rules are 17900 precisely the same as for PERSON1, so we have: 17950 .ASIS 18000 18050 INTEGER PROCEDURE PERSON2 (INTEGER VALUE N); 18100 IF N=0 THEN 1 ELSE N*PERSON3(N-1); 18150 18200 .END 18250 We could go on and on writing such procedures. However, 18300 we notice that all the procedures are identical except that they call 18350 upon different PERSONs to solve the simpler problems. ALGOL W 18400 permits us to define only one PERSON, and ALGOL W 18450 will copy the definition if a new PERSON is required. Let us name 18500 this person FACTORIAL: 18600 .ASIS 18650 18700 INTEGER PROCEDURE FACTORIAL (INTEGER VALUE N); 18750 IF N=0 THEN 1 ELSE N*FACTORIAL(N-1); 18800 18825 .;GARBAGE45 18850 .END 18900 The use of FACTORIAL(N-1) (second line) in evaluating FACTORIAL(n) 18950 will cause creation of a new copy of the rules for 19000 factorial (i.e. will create a new person) in order to compute 19050 the value of FACTORIAL(N-1). When each copy returns 19100 its answer, the copy is automatically destroyed. 19150 Thus our drawing of stick figures now turns into a drawing of prcedure 19200 copies, each with the same rules, but a different value of N: 19250 .;THIS3875 19300 .ASIS 19350 19400 FACTORIAL(3) 19450 IF 3=0 THEN 1 ELSE 3*FACTORIAL(2) 19500 19550 FACTORIAL(2) 19600 IF 2=0 THEN 1 ELSE 2*FACTORIAL(1) 19650 19700 FACTORIAL(1) 19750 IF 1=0 THEN 1 ELSE 1*FACTORIAL(0) 19800 19850 FACTORIAL(0) 19900 IF 0=0 THEN 1 ELSE 0*... 19950 20000 20050 20100 20150 .END 20200 The dotted lines show the values returned by each copy of 20250 FACTORIAL. 20300 We will now demonstrate the sequence of steps actually 20350 performed by the computer. Let us label the minute steps of the 20400 FACTORIAL procedure as follows: 20450 .BEGIN INDENT 6,2 20500 .SK 1 20550 F.1#Test to see if N is zero. If true, go to step F.2, otherwise to step F.3 20600 20650 F.2#Return the answer "1" to the procedure that called us, and 20700 destroy this copy of FACTORIAL. 20750 20800 F.3#Compute the value of N-1. 20850 20900 F.4#Create a new copy of the rules for FACTORIAL. Initialize it so 20950 that its value of N contains the expression computed in step 21000 F.3. Remember that the next step we must execute when the copy returns 21050 an answer is step F.5. Now go perform step F.1 21100 of the new copy, and proceed. 21150 21200 F.5#We come to this step when an answer has been returned 21250 by a copy of FACTORIAL. Multiply the answer by N. 21300 21350 F.6#Return this new expression to the procedure that called 21400 us and destroy this copy of FACTORIAL. 21450 .SK 1 21500 .END 21550 If, in the main program, we issued a command 21600 .ASIS 21650 21700 I := FACTORIAL (3) 21750 21800 .END 21850 ALGOL W creates a copy of FACTORIAL with N=3, and starts at step 21900 F.1 of the copy: 21950 .ASIS 22000 22050 F.1 Is 3=0? No, execute step F.3 next. 22100 F.3 3-1 = 2 22150 F.4 Create a new copy of FACTORIAL with N=2; our next step will 22200 be F.5 when an answer is returned. Now go to step F.1 of the copy. 22250 F.1 Is 2=0? No, execute step F.3 next. 22300 F.3 2-1 = 1 22350 F.4 Create copy with N=1; our next step is F.5; go to copy. 22400 F.1 Is 1=0? No, execute step F.3 next. 22450 F.3 1-1 = 0 22500 F.4 Create copy with N=0; our next step is F.5; go to copy. 22550 F.1 Is 0=0? Yes, execute step F.2 22600 F.2 Return "1" to our caller (i.e. let him pick up computing 22650 where he left off) and destroy this copy of FACTORIAL. 22700 F.5 answer*n = 1*1 = 1 22750 F.6 Return 1 to our caller and destroy this copy. 22800 F.5 answer*n = 1*2 = 2 22850 F.6 Return 2 to our caller, and destroy this copy. 22900 F.5 answer*n = 2*3 = 6 22950 F.6 Return 6 to our caller, and destroy this copy. This will cause 23000 the value of 6 to be returned to the place in the main prograa that 23050 called FACTORIAL(3), and thus stored in I. 23100 23150 .END 23200 We can verify that ALGOL W behaves this way with 23250 the following program: 23300 .ASIS 23350 23400 BEGIN 23450 INTEGER PROCEDURE FACTORIAL (INTEGER VALUE N); 23500 BEGIN INTEGER ANSWER; 23550 WRITE ("COPY CREATED TO COMPUTE FACTORIAL OF",N); 23600 IF N=0 THEN ANSWER:=1 ELSE ANSWER:=N*FACTORIAL(N-1); 23650 WRITE ("ANSWER TO FACTORIAL OF",N,"IS",ANSWER); 23700 ANSWER 23750 END; 23800 23850 INTFIELDSIZE := 2; 23900 WRITE (FACTORIAL(3),"IS THE ANSWER"); 23950 END. 24000 24050 .END 24100 You may want to try this on the computer. The output 24150 will look like: 24200 .ASIS 24250 24300 COPY CREATED TO COMPUTE FACTORIAL OF 3 24350 COPY CREATED TO COMPUTE FACTORIAL OF 2 24400 COPY CREATED TT COMPUTE FACTORIAL OF 1 24450 COPY CREATED TO COMPUTE FACTORIAL OF 0 24500 ANSWER TO FACTORIAL OF 0 IS 1 24550 ANSWER TO FACTORIAL OF 1 IS 1 24600 ANSWER TO FACTORIAL OF 2 IS 2 24650 ANSWER TO FACTORIAL OF 3 IS 6 24700 6 IS THE ANSWER 24750 24800 .END 24850 .SK 2 24900 ↓_Example 3: Counting Leaves of a Tree_↓ 24950 25000 Suppose that it its your task to count the number of leaves on a 25050 binary tree: 25100 .FIG 5 25150 A binary tree is one that can only branch two ways at each 25200 junction: 25250 .ASIS 25300 .FIG 3 25350 Binary junction 3 branches more branches! 25400 .SK 1 25450 .END 25500 Although you can count the number of leaves on the above tree 25550 very easily, if the tree got very much bigger, even 25600 humans would have trouble keeping things straight (Have I counted this 25650 branch already?). However, the recursive technique is very simple. 25700 Start at the trunk of the tree (sometimes called the "root") and 25750 use the following rules: 25800 .BEGIN INDENT 6,3 25850 .SK 1 25900 1.#If you hold in your hand a "leaf" (#####), then the answer is "1" 25950 (i.e. there is one leaf on the tree). 26000 26050 2.#Otherwise, you must hold a branch. Break the branch in two places: 26100 .FIG 4 26150 and find a person willing to follow these same rules. Give him/her 26200 piece A and wait for the answer. Remember it as 26250 ANSWERA. Then give the person piece B and wait for an answer, remembered 26300 as ANSWERB. Now you can compute the answer to the original 26350 question: it is just ANSWERA+ANSWERB. This follows because 26400 the answer ANSWERA is (we hope) the number of leaves on 26450 piece A, and ANSWERB is the number of leaves on piece B. Clearly the 26500 total number of leaves on the original branch is just the sum of these 26550 two numbers. 26600 .END 26650 .SK 1 26700 Once again, this formulation uses the recursive paradigm. We can now 26750 give a skeleton ALGOL W procedure that implements these rules: 26800 .ASIS 26850 26900 INTEGER PROCEDURE TREECOUNT ( branch ); 26950 IF branch = leaf THEN 1 ELSE 27000 TREECOUNT( left(branch) )+ TREECOUNT ( right(branch) ); 27050 27100 .END 27150 Of course ALGOL W can't handle branches, leaves, and left and right 27200 branches directly. Instead we must ?!represent?! the tree in some 27250 form that ALGOL W can manipulate. We shall demonstrate two 27300 representations, one using arrays and one using records and 27350 references. 27400 27450 Suppose that each branch is given a unique integer number. Then 27500 we set up two integer arrays LEFTBRANCH and RIGHTBRANCH. For 27550 the tree: 27600 .FIG 6 27650 we have 27700 .ASIS 27750 27800 LEFTBRANCH(1) = 3 RIGHTBRANCH(1) = 2 27850 LEFTBRANCH(2) = 0 RIGHTBRANCH(2) = 0 27900 LEFTBRANCH(3) = 4 RIGHTBRAHCH(3) = 5 27950 LEFTBRANCH(4) = 0 RIGHTBRANCH(4) = 0 28000 LEFTBRANCH(5) = 0 RIGHTBRANCH(5) = 0 28050 28100 .END 28150 This representation says that branch 1 divides into branches 3 28200 (LEFTBRANCH(1)) and 2 (RIGHTBRANCH(1)). However, branch 4 does not 28250 divide (LEFTBRANCH(4) = 0, RIGHTBRANCH(4) = 0) and is therefore 28300 a leaf. 28350 28400 This representation 28450 allows us to write the TREECOUNT procedure as follows: 28500 .ASIS 28550 28600 INTEGER ARRAY LEFTBRANCH,RIGHTBRANCH (1::20); 28650 28700 INTEGER PROCEDURE TREECOUNT (INTEGER VALUE BRANCH); 28750 IF LEFTBRANCH(BRANCH)=0 THEN 1 ELSE 28800 TREECOUNT(LEFTBRANCH(BRANCH))+TREECOUNT(RIGHTBRANCH(BRANCH)); 28850 28900 COMMENT Setup arrays LEFTBRANCH and RIGHTBRANCH here; 28950 29000 WRITE ("NUMBER OF LEAVES IS",TREECOUNT(1)); 29050 29100 .END 29150 A representation using records and references might be as 29200 follows: we set up a record named TWIG that has two references 29250 to other such records: LEFT and RIGHT. 29300 .ASIS 29350 29400 RECORD TWIG ( REFERENCE (TWIG) LEFT,RIGHT ); 29450 REFERENCE (TWIG) TRUNK; 29500 29550 INTEGER PROCEDURE TREECOUNT (REFERENCE(TWIG) BRANCH); 29600 IF LEFT(BRANCH)=NULL THEN 1 ELSE 29650 TREECOUNT(LEFT(BRANCH))+TREECOUNT(RIGHT(BRANCH)); 29700 29750 COMMENT Setup records to represent the tree here. Assume that 29800 TRUNK is a reference to the twig that represents the trunk.; 29850 29900 WRITE ("NUMBER OF LEAVES IS",TREECOUNT(TRUNK)); 29950 30000 .END 30050 You may wish to hand compute the answer using the following record 30100 structure (same tree as used in the array example above): 30150 .ASIS 30200 30250 TRUNK ----> LEFT -------> LEFT -------> LEFT NULL 30300 RIGHT RIGHT RIGHT NULL 30350 30400 LEFT NULL LEFT NULL 30450 RIGHT NULL RIGHT NULL 30500 30550 .END 30600 This example is the first in which the recursive algorithm is actually 30650 easier to formulate than an iterative form (If you don't believe this, 30700 try to write a non-recursive version of the treecount procedure with 30750 records and references used to represent the tree structure). 30800 30850 ↓_Example 4: Counting Miles_↓ 30900 30950 The design of recursive procedures is not always as easy as in the examples 31000 above. We have to be particularly careful to avoid "infinite recursion" 31050 just as we have to be careful to avoid "infinite looping" in commands 31100 like: 31150 .ASIS 31200 31250 WHILE 2<3 DO WRITE ("LOOP"); 31300 31350 .END 31400 Infinite recursion occurs when we are not adequately careful in 31450 formulating the "simpler problem." For example, if solving problem A 31500 requires solving simpler problem A', which in turn requires solving 31550 "simpler" problem A, we are in trouble! The following example illustrates 31600 this danger. 31650 31700 Suppose we have a road map represented by an array of zeroes and ones: 31750 .ASIS 31800 .INDENT 20,20 31850 31900 10100000000 31950 10100000000 32000 11110001000 32050 00100001000 32100 00111001010 32150 00001111010 32200 01000001010 32250 11110000110 32300 32350 .END 32400 We are to start in our car at the upper left-hand corner of the map 32450 and follow roads (represented by 1's) to find out how many miles of raod 32500 can be reached from the upper left-hand corner (each 1 represents a 32550 mile of road). If there is a road at one location, then we must check 32600 to see if it extends to the top, bottom, left or right of the square. 32650 In other words, the squares marked "a" are accessible from that marked 32700 "x": 32750 .ASIS 32800 .INDENT 25,25 32850 32900 a 32950 axa 33000 a 33050 33100 .END 33150 Let us number rows of the matrix ROAD from i=1 to 8 (top to 33200 bottom) and columns from j=1 to 11 (left to right). 33250 33300 We can formulate an answer to the problem as follows: 33350 suppose we write a procedure FOLLOW that takes two arguments, 33400 row number i and column number j. FOLLOW is to return the number 33450 of miles of road that can be reached from position (i,j). 33500 The answer to the problem will then be simply: 33550 .ASIS 33600 33650 WRITE ("NUMBER OF MILES IS",FOLLOW(1,1)); 33700 33750 .END 33800 What are the commands that FOLLOW must contain? Clearly if ROAD(i,j)=0, 33850 then the answer is zero: there is no road in this square. 33900 Otherwise, the answer can be obtained by adding 1 (for the square 33950 we are on) to the results of FOLLOWing road in the four directions 34000 that can be accessed from our square (i,j): 34050 .ASIS 34100 34150 1+FOLLOW(I-1,J)+FOLLOW(I+1,J)+FOLLOW(I,J-1)+FOLLOW(I,J+1) 34200 34250 .END 34300 But we notice one "bug" right away: evaluating FOLLOW(1,1) 34350 will require evaluating 34400 .ASIS 34450 .INDENT 10,10 34500 34550 FOLLOW(0,1) 34600 FOLLOW(2,1) 34650 FOLLOW(1,0) 34700 FOLLOW(1,2) 34750 34800 .END 34850 but if i or j are zero we have gone off the road map! We can fix this 34900 problem by contriving to answer that FOLLOWing any road off the map 34950 yields a route length of zero. Now we have: 35000 .ASIS 35050 35100 INTEGER ARRAY ROAD(1::8,1::11); 35150 35200 INTEGER PROCEDURE FOLLOW (INTEGER VALUE I,J); 35250 BEGIN INTEGER ANSWER; 35300 IF I=0 OR I=9 OR J=0 OR J=12 THEN ANSWER := 0 ELSE 35350 IF ROAD(I,J)=0 THEN ANSWER := 0 ELSE 35400 ANSWER := 1+FOLLOW(I-1,J)+FOLLOW(I+1,J)+FOLLOW(I,J-1)+FOLLOW(I,J+1); 35450 ANSWER 35500 END; 35550 35600 .END 35650 But alas, this procedure will never return an answer to 35700 FOLLOW(1,1)! We have generated a program that will recur infinitely. 35750 Luckily, there is a time limit on your program's runtime that will 35800 expire before you consume hours of computer time. 35850 35900 To see why the program doesn't work properly, we shall "hand simulate" 35950 the FOLLOW procedure using the road map shown above. We shall draw 36000 the computation with a diagram: a procedure call FOLLOW(i,j) 36050 will be indicated by i and j inside parentheses. 36100 Thus (1,1) represents a call FOLLOW(1,1). 36150 Since ROAD(1,1)=1, the first two IF commands of the FOLLOW procedure 36200 do not pertain, and we must evaluate FOLLOW(0,1), FOLLOW(2,1), 36250 FOLLOW(1,0) and FOLLOW(1,2) in order to compute an answer. 36300 This is indicated diagramatically as follows: 36350 .ASIS 36400 36450 (1,1) 36500 36550 (0,1) (2,1) (1,0) (1,2) 36600 36650 .END 36700 Now we shall underline (___) those cases that return zero, either 36750 because i or j is off the map or because ROAD(i,j)=0: 36800 .ASIS 36850 36900 (1,1) 36950 37000 ↓_(0,1)_↓ (2,1) ↓_(1,0)_↓ ↓_(1,2)_↓ 37050 37100 .END 37150 Now, in computing (2,1), we request four more FOLLOW computations: 37200 .ASIS 37250 37300 (1,1) 37350 37400 ↓_(0,1)_↓ (2,1) ↓_(1,0)_↓ ↓_(1,2)_↓ 37450 37500 (1,1) ↓_(3,1)_↓ ↓_(2,0)_↓ ↓_(2,2)_↓ 37550 37600 37650 .END 37700 This little exercise has uncovered the problem! In order to evaluate 37750 (1,1), we need to evaluate (1,1). The trouble is that when (2,1) 37800 tries to explore neighboring squares, it returns to (1,1) which has 37850 already been explored. 37900 37950 One way to fix this problem is to "erase road" as we explore. 38000 This will prevent exploration of already-explored road. 38050 FOLLOW becomes: 38100 .ASIS 38150 38200 INTEGER PROCEDURE FOLLOW (INTEGER VALUE I,J); 38250 BEGIN INTEGER ANSWER; 38300 IF I=0 OR I=9 OR J=0 OR J=12 THEN ANSWER := 0 ELSE 38350 IF ROAD(I,J)=0 THEN ANSWER := 0 ELSE 38400 BEGIN 38450 COMMENT First erase the road under us so that any subsequent 38500 explorations of this square will answer zero.; 38550 ROAD(I,J) := 0; 38600 ANSWER := 1+FOLLOW(I-1,J)+FOLLOW(I+1,J)+ 38650 FOLLOW(I,J-1)+FOLLOW(I,J+1) 38700 END; 38750 ANSWER 38800 END; 38850 38900 .END 38950 Now, since FOLLOW(1,1) sets ROAD(1,1) to zero, our diagram becomes: 39000 .ASIS 39050 39100 (1,1) 39150 39200 ↓_(0,1)_↓ (2,1) ↓_(1,0)_↓ ↓_(1,2)_↓ 39250 39300 ↓_(1,1)_↓ (3,1) ↓_(2,0)_↓ ↓_(2,2)_↓ 39350 39400 ↓_(2,1)_↓ ↓_(4,1)_↓ ↓_(3,0)_↓ (3,2) 39450 39500 39550 .END 39600 Notice that we have now underlined the second attempt to explore 39650 (1,1); since we set ROAD(1,1) to zero at the first attempt, the 39700 second attempt will now safely return zero, and will not attempt 39750 to explore all routes leading out of square (1,1) etc. 39800 39850 ↓_Example 5: Finding a Route_↓ 39900 39950 Example 4 actually suggests a way for finding a routine from one spot 40000 on our map to another. We notice from the branching diagram that the 40050 branches seem to follow along (1,1), (2,1), (3,1), (3,2) ... which 40100 is in fact a sequence of steps along the road. All we need to do is 40150 provide a mechanism for (a) deciding when we have reached the destination 40200 we seek and (b) then printing out the correct route. 40250 40300 We can accomplish (a) by comparing i and j to two global variables 40350 IDESTINATION and JDESTINATION. If both are equal, we have reached 40400 the destination. We shall change FOLLOW to be a LOGICAL procedure, and 40450 it will return TRUE if there is a route to the destination. We shall 40500 print out the route as we return through the recursive procedure 40550 calls: 40600 .ASIS 40650 40700 INTEGER IDESTINATION,JDESTINATION; 40750 INTEGER ARRAY ROAD (1::8,1::12); 40800 40850 LOGICAL PROCEDURE FOLLOW (INTEGER VALUE I,J); 40900 BEGIN LOGICAL ANSWER; 40950 IF I=0 OR I=9 OR J=0 OR J=12 THEN ANSWER := FALSE ELSE 41000 IF ROAD(I,J)=0 THEN ANSWER := FALSE ELSE 41050 BEGIN 41100 IF I=IDESTINATION AND J=JDESTINATION THEN 41150 BEGIN 41200 WRITE ("(",I,",",J,")"); 41250 ANSWER := TRUE; 41300 END ELSE BEGIN 41350 ROAD(I,J) := 0; 41400 COMMENT First search above; 41450 ANSWER := FOLLOW(I-1,J); 41500 COMMENT If no route that way then search below; 41550 IF ¬ANSWER THEN ANSWER := FOLLOW(I+1,J); 41600 COMMENT If still no route then search to the left; 41650 IF ¬ANSWER THEN ANSWER := FOLLOW(I,J-1); 41700 COMMENT If still no route then search to the right; 41750 IF ¬ANSWER THEN ANSWER := FOLLOW(I,J+1); 41800 COMMENT If any of the paths succeeded, then this spot (i,j) 41850 is on the successful route! Print it out.; 41900 IF ANSWER THEN WRITE ("(",I,",",J,")"); 41950 END 42000 END; 42050 ANSWER 42100 END; 42150 42200 COMMENT Set up the array ROAD here; 42250 IDESTINATION := 4; JDESTINATION := 8; 42300 42350 COMMENT Now call FOLLOW. If it returns FALSE, there was no route.; 42400 IF ¬FOLLOW(1,1) THEN WRITE ("YOU CAN'T GET THERE FROM HERE"); 42450 42500 .END 42550 If we use the road map given above, the route will be printed 42600 out (in reverse) as follows: 42650 .ASIS 42700 .INDENT 10,10 42750 42800 (4,8) 42850 (5,8) 42900 (6,8) 42950 (6,7) 43000 (6,6) 43050 (6,5) 43100 (5,5) 43150 (5,4) 43200 (5,3) 43250 (4,3) 43300 (3,3) 43350 (3,2) 43400 (3,1) 43450 (2,1) 43500 (1,1) 43550 43600 .END 43650 This procedure illustrates a ↓_searching_↓ technique. 43700 The philosophy of resursive search is as follows: 43750 .BEGIN INDENT 6,3 43800 .BEGIN INDENT 6,3 43850 .SK 1 43900 1.#Check to see if we are at the goal location. If so, return 43950 TRUE. 44000 44050 2.#Otherwise, try to solve one of several simpler search problems by 44100 taking a small motion in one of the available directions and applying 44150 the rules recursively. 44200 .END 44250 .SK 1 44300 We must of course be sure that the searches don't loop. 44350 In the FOLLOW example above, we actually took a slightly different 44400 approach than the search paradigm above: step 2 was divided into two 44450 parts (2a) try all potentially legal paths from this location and 44500 (2b) verify that a potential path is legal (on the map and ROAD(i,j) 44550 non-zero). Then we wrote the procedure as follows: 44600 .BEGIN INDENT 6,3 44650 .SK 1 44700 2b:#If this (i,j) proposed path is not legal, return FALSE. 44750 44800 1.#If we are at the goal, return TRUE. 44850 44900 2a.#Try each potential path from this location. If ↓_any_↓ 44950 of the trials returns TRUE, we have found a path. In that case, 45000 print out (i,j) since it is on the path, and return TRUE. 45050 If none of the trials returns TRUE, then we must return FALSE. 45100 .END 45150 .SK 2 45200 ↓_Concluding Remarks_↓ 45250 45300 Recursion is a very powerful programming technique as well as a way of 45350 formullting many problems, whether for human or computer solution. 45400 The examples we have given have only scratched the surface of the 45450 technique. 45500 45550 Many people berate recursion because it is inefficient: all that 45600 "copying" of procedures! In fact, most programming languages that 45650 permit recursion arrange to copy only a very small amount of information 45700 each time a procedure is called. Nevertheless, in ALGOL W, the 45750 recursive method of computing the factorial is substantially more 45800 inefficient (slower) than the iterative method. 45850 An iterativeform of factorial is probably just as easy to understand 45900 as a recursive form. However, for problems like Examples 3, 4 and 5, 45950 the recursive formulation is substantially simpler than formulations 46000 not using recursion (try it). Thus we achieve a certain 46050 "programmer efficiency"; and in these cases the non-recursive solutions 46100 require more ALGOL W commands than the recursive formulations, and 46150 the recursive from may not be any slower than the non-recursive 46200 form. 46250 46300 Different programming languages take different attitudes about 46350 recursion. FORTRAN, for example, does not permit it. 46400 (The language does not copy procedures when they are called. This 46450 prevents recursion from working properly. Why? Consider what would 46500 happen if only one "copy" of FACTORIAL were available.) 46550 Languages such as ALGOL W, PL/I and CHIRON all permit recursion, 46600 but the cost of recursion is higher than that of, say, iteration. 46650 The LISP language is structured to actively encourage recursion; 46700 in fact recursive formulations are often clearer and more efficient 46750 than iterative ones. 46800 46850 Many programmers who use recursion frequently start 46900 to "think recursively" when formulating computer programs or 46950 algorithms. Some of the most powerful and impressive computer 47000 programs (programs that play chess, that "understand" English 47050 sentences, or that compile languages such as ALGOL W into 47100 machine-language) are based on recursive algorithms. 47150 We close with the light-hearted remark attributed to 47200 Peter Deutsch, a virtuoso programmer, 47250 47300 "To iterate is human, to recurse divine." 47350 .NEXT PAGE 47400 47450 47500 ↓_Exercises_↓ 47550 47600 1. Write a recursive procedure that will have the same effect as the 47650 ALGOL W skeleton 47700 .ASIS 47750 47800 FOR I := LOWER UNTIL UPPER DO 47850 command 47900 47950 .END 48000 LOWER and UPPER are integer variables, and "command" is some ALGOL W command. 48050 48100 2. Formulate a solution to Example 3, records and references representation, 48150 that uses no procedures (i.e. a non-recursive solution). Be careful 48200 to try your program on a variity of trees; also state the conditions 48250 under which your program will not get a correct answer. 48300 48350 3. What if the tree (Example 3) isn't binary? Formulate 48400 a solution in which a twig may have 0, 1, 2, or 3 branches leaving it. 48450 48500 4. Modify FOLLOW (Example 4) so that it does not permanently 48550 destroy the information in the ROAD array. Be careful that the 48600 modified procedure will not recur infinitely. (Hint: you need to 48650 add only one ALGOL W command to FOLLOW to solve this problem.) 48700 48750 5. Arrange to print out the route (Example 5) in the correct orcer. 48800 You might also plot a "map" of the route. 48850 48900 6. The program of example 5 will not always find the shortest 48950 route from starting point to the goal. 49000 Construct a road map for which this is the case. Modify FOLLOW so that 49050 it will find the optimal (shortest) route. 49100 49150 7. ↓_Blob counting._↓ Suppose we haae an array representation of an image 49200 of (say) blood cells. We wish to count the number of separate "blobs" 49250 in the image and to measure their sizes. The rules for blobs are as 49300 follows: if a square "x" is in a blob, so may be those marked "a": 49350 .ASIS 49400 .INDENT 20,20 49450 49500 aaa 49550 axa 49600 aaa 49650 49700 .END 49750 The size of a blob is just the number of squares in it. For example, 49800 .ASIS 49850 .INDENT 15,15 49900 49950 00110010 50000 01111010 50050 11110011 50100 11100111 50150 01000110 50200 00011010 50250 50300 .END 50350 has two blobs of 1's: one is of size 14, one of size 12. 50400 Arrange your program to read in (from data cards) the 50450 dimensions of the image area and the values of the elements 50500 of the array. 50550 50600 8. The technique of setting ROAD(i,j) to zero to prevent 50650 infinite recursion doesn't work when the problem is represented 50700 with records and references. Consider trying to search from START 50750 to GOAL in the following structure: 50800 .FIG 15 50850 Design a procedure that will perform the search correctly and that 50900 will leave the structure intact when it is finished. 50950 51000 9. (After solving problem 8) ↓_Telephone Line Connections_↓ 51050 A telephone network might look as follows: 51100 .FIG 10 51150 The circles represent switching offices, and the number represent 51200 the capacity (in simultaneous conversations) of each connection. 51250 The telephone company has discovered that the "best" path is 51300 one that minimizes the value of 51350 .ASIS 51400 51450 N + 50/capacity_of_link 51500 51550 .END 51600 where N is the number of intermediate switching offices on the path, 51650 and the sum is taken over all telephone links on the path. Find the 51700 optimal path from A to B in the above network. 51750 51800 .END 51850 .END 51900 .END 51950 .END