ۥ-/@ -4>VO;cT`T``TpTTTTTfZUZUZUZUZU dU:ZUUUUUUUUUUUUUUUUUUV4KVRVTfVV ! Recursive Procedures in Languages That Do Not Support Recursion by Aaron Banerjee A recursive procedure is a procedure which invokes itself. While this is not a particularly complicated idea, recursion is one of the more awkward concepts in computer programming. Why would anyone write a recursive procedure? How is recursion used to solve problems? After all, anything a recursive procedure can do can also be done with non-recursive techniques. Although recursive procedures are never the only way to solve a problem, in certain cases, they may be the most intuitive or convenient. Consider the Fibonacci series, which is a series of numbers which appear in certain biological phenomena. 1,1,2,3,5,8,13,... The first two terms are 1. Every term after that is the sum of the preceding two terms (1+1=2, 1+2=3, 3+5=8, etc.). This can be described with a recursive procedure: f(n+2) = f(n) + f(n+1) where f(1)=1, f(2)=1 This can easily be implemented in C code: int fibonacci(int n) { int q; if ((n==1)||(n==2)) q=1 else q=fibonacci(n-1)+fibonacci(n-2); return (q); } The corresponding code in TRS-80 Color Computer BASIC (shown below) would not run properly because (among other things), changing the value of N in one "iteration" will change it in every other. The C language (in versions which support recursion) "remember" the state of the previous iteration. 10 REM Calculate Fibonacci Numbers (doesn't work) 15 REM Input N, output Q 20 IF N=1 OR N=2 THEN Q=1 ELSE N=N-1:GOSUB 10:Z=Q:N=N-1:GOSUB 10:Q=Z+Q 30 RETURN In order to make this work recursively, we would need a more complex BASIC program. In the simple case of Fibonacci numbers: f(n+2)=f(n+1)+f(n) : f(0)=1, f(1)=1 it is better to solve the difference equation instead of worrying about recursion. Besides, on small computers that operate at 0.9 MHZ, you don't want to do any iterations you don't have to. The following program prints out the first 10 Fibonacci numbers in closed form: 5 CLS 10 REM FIBONACCI NUMBERS = FNF(N) 15 F1=(1+SQR(5))/2:F2=(1-SQR(5))/2 20 D = F2 - F1 25 A=(F2 - 1)/D:B=(1-F1)/D 30 DEF FNF(N)=INT(.5+A*F1^N + B*F2^N) 35 FOR N=0 TO 10:PRINT N,FNF(N):NEXT N The above program works rapidly on a TRS-80 Color Computer and for large numbers, even faster than a 486 25 MHz system running the recursive technique. This isn't a fair comparison because we didn't do a recursive approach. Instead, we simply found a totally different approach to solve the same problem. In general, there is a way around recursion, but sometimes recursion can be the simplest way to solve a problem. Consider a more challenging example: One of the most famous recursive problems is the "eight queens" problem. The object is to find each and every way one can place eight queens on a chess board without having any one queen being able to attack any other. For those unfamiliar with chess, a chess board is an 8x8 matrix. A queen can move any number of spaces vertically, horizontally, or diagonally. A queen may attack any other piece which is on a square that the queen can move to. One obvious solution to this is to do an exhaustive search. Set up an array and keep placing queens on it until none of them can attack each other. Placing queens at random gives you 64*63*62*61*60*59*58*57 = 1.78 x 1014 possibilities, which would probably take years on the Coco. There is a recursive algorithm which is known to solve the eight queens problem. "The problem can be solved with a recursive procedure having two parameters--some representation of the chess board and an integer in the range zero to eight. When the procedure is called with the integer parameter having some value n, it is assumed that an acceptable placement has been found for queens in the first n columns of the chessboard. Thus if n is eight, the procedure should just print out the arrangement of queens on the chessboard and return. If n is less than eight, the program should try to place a queen in each of the eight squares of column n+1 in turn, and check whether a queen on that square is in the same row, left-to-right ascending diagonal, or left-to-right descending diagonal as a queen in some previous column. If this check reveals no conflicts with any queens in previous columns, the procedure should call itself recursively with the chessboard representation having a queen on that square and the integer parameter equal to n+1, to try to fill in the remaining columns." From our exercise above with Fibonacci numbers, we see that the Coco does not lend itself particularly well to recursive procedures and furthermore, this time, however, there isn't a simple way out. In order to solve this problem recursively, first we have to solve the problem of the Coco not being able to recurse. One of the main reasons why the attempt at recursion in BASIC for the Fibonacci series (above) did not work is that all of the variables and states are global. The C example, on the other hand, stores the state before invoking the next iteration. An obvious solution would be to emulate a stack so that the program could "remember where it left off" before recursing, and restoring the state upon return (except for the quantity which was to be changed). Actually, some Coco functions do "remember where they left off". Try this short program and run it. 5 PRINT MEM 10 GOTO 5 Not very impressive. It simply prints your available memory (20805 in my case) and repeats it. Now try this one: 5 PRINT MEM 10 GOSUB 5 Run it and watch as your computer unceremoniously runs out of memory and gives you an ?OM ERROR. Every time you GOSUB, the computer has to use some memory to remember where you GOSUB'ed from so that when it encounters a RETURN, it will return to the correct place. If you had pressed before running out of memory, you would be able to type RETURN several times (as many as the program had cycled) without getting an ?RG ERROR. The trick to recursion on the Coco is to save everything which is needed instead of just return addresses. The following is a solution to the eight queens problem written in Coco BASIC. 10 CLS 20 GOSUB 600 30 CLEAR 40 DIM YS(10),NS(10),B(8,8) 50 SP=0:BC=0 60 REM 70 REM 80 REM MAIN PROGRAM 90 REM 100 N=0:GOSUB 380 110 PRINT"YEE HA!" 120 END 130 REM CLEAR THE BOARD 140 FOR IC=1 TO 8:FOR JC=1 TO 8 150 B(IC,JC)=0 160 NEXT JC,IC 170 RETURN 180 REM CHECK FUNCTION 190 REM INPUT N,Y 200 REM OUTPUT C=0 (FALSE) 1=TRUE 210 REM 220 C=1 230 FOR IC=1 TO N-1:FOR JC=1 TO 8 240 IF B(IC,JC)=0 THEN 270 250 IF IC=N OR JC=Y THEN C=0 260 IF ABS(IC-N)=ABS(JC-Y) THEN C=0 270 NEXT JC,IC 280 RETURN 290 REM PUSH Y AND N 300 REM 310 SP=SP+1:NS(SP)=N:YS(SP)=Y 320 RETURN 330 REM PULL Y AN N 340 REM 350 N=NS(SP):Y=YS(SP):SP=SP-1 360 RETURN 370 REM 380 REM PLACE FUNCTION (RECURSIVE) 390 REM 400 IF N>=8 THEN GOSUB 490:GOTO 460 410 N=N+1 420 FOR Y=1 TO 8 430 GOSUB 180 440 IF C THEN B(N,Y)=1:GOSUB 290:GOSUB 380 450 NEXT Y 460 GOSUB 330 470 B(N,Y)=0 480 RETURN 490 REM DRAW BOARD 500 CLS:BC=BC+1:PRINT"BOARD "BC:PRINT:PRINT 510 PRINTTAB(10)"EIGHT QUEENS":PRINT 520 PRINT" " STRING$(26,128) 530 FOR JC=1 TO 8 540 PRINT " "CHR$(128); 550 FOR IC=1 TO 8 560 IF B(IC,JC)=1 THEN PRINT" Q "; ELSE PRINT " - "; 570 NEXT IC: PRINT CHR$(128): NEXT JC 580 PRINT " "STRING$(26,128) 590 RETURN 600 REM INTRO 610 REM 620 CLS 630 PRINT 640 PRINTTAB(9)"EIGHT QUEENS" 650 PRINTTAB(7)"BY AARON BANERJEE" 660 PRINT:PRINT 670 PRINT"THIS PROGRAM FINDS ALL POSSIBLE" 680 PRINT"WAYS TO PLACE 8 QUEENS ON A " 690 PRINT"CHESS BOARD WITHOUT ALLOWING " 700 PRINT"ANY QUEEN TO ATTACK ANY OTHER." 710 PRINT:PRINT"PLEASE BE PATIENT. THE PROGRAM" 720 PRINT"IS EXTREMELY SLOW (SEVERAL " 730 PRINT"MINUTES FOR THE FIRST BOARD)" 740 PRINT 750 INPUT"PRESS ENTER TO BEGIN";A$ 760 RETURN This program executes the recursive algorithm for solving the 8 queens problem. The representation of the board is the B(8,8) array. Each element has a value of 1 if there is a queen present, 0 if not. The value N is the integer whose value is from 0 to 8. To start the program, N is given a value of 0 and the subroutine is called. Let us now consider operation of the program. As mentioned before, N is set to zero and the Place procedure (line 380) is invoked. The algorithm calls for each square in the N+1 column (column 1 in this case) to be checked. In this design, to check the N+1 column, N is incremented by 1 and a FOR Y loop is set up in line 420 to start the count. The first time the check function is called from line 430, it will be checking to see if any queen can attack square 1,1. Since there aren't any queens on the board yet, the check function will set C=1. Line 440 places a queen at the location (1,1). The algorithm states that at this point the procedure should be recursively called for the next (N+1 = 2) column. If we do that, we will be altering the value of N. In addition, we haven't completed the FOR Y loop yet, which will cause problems. At this point, the board should look like this: Q                                                                         In this example, the upper left corner is taken as square 1,1. The column number (N) progresses to the right, the row number (Y) progresses downward. In line 440, we push Y and N on a simulated stack and GOSUB 380 (calls the Place function from itself). In the second iteration, N is incremented to 2 and a new FOR Y loop is started. The computer has forgotten about the old FOR Y, but this will be dealt with shortly. The new FOR Y loop looks at square 2,1 (to the right of the previous queen). This is not acceptable so it checks 2,2 (also unacceptable). Square 2,3 will check out (C=1) so a queen is placed there. The board now appears like this: Q                   Q                                                      Again the procedure will push the values of Y and N (2,3) onto the stack (on top of the 1,1 pushed previously). This process will keep repeating and pushing Y and N on the stack until the following pattern is encountered: Q            Q       Q            Q       Q                                   At this point the stack will have (1,1), (2,3), (3,5), and (4,2). It will push (5,4) onto the stack and GOSUB 380 again. This time, there will be no spaces in the N=6 column where a queen can be placed with out being able to attack any other. The NEXT Y will be reached. The program then pulls N=5,Y=4 from the stack. Since there were no good places to place a queen in the sixth row with the position of the first 5, the queen at 5,4 is removed in line 470. Since we called Place (line 380) from line 440, the RETURN in line 480 will not return us from the subroutine, but rather back to line 450. Although we have already exited the FOR Y loop, we have reset the counter Y back to 5 and jumped back in. NEXT Y is not that smart and will not realize we've ever left. This is an unorthodox technique that is generally frowned upon because different BASIC interpreters may react differently. Computer programmers who disdain the use of GOTO would probably consider jumping in and out of FOR loops and altering the counter anything from "spaghetti code" to blasphemy. In order to get recursion in non-recursive environments, some unconventional techniques are necessary. In any event, the location of the last queen (5,4) was pulled from the stack and removed from the board. The NEXT Y in line 450 increments Y to 6 and the next square is checked. Notice that we've fooled the computer into going back to where it was in the N=5 row when it left. The computer will find another place to place a queen at (5,8) but again there will be no safe place to put a queen on the N=6 row. This is shown below: Q            Q       Q                   Q                             Q      The computer will pull the (5,8) from the stack and remove the queen, and then pull the (4,2) from the stack (N=4, Y=2) and remove that queen. When the NEXT Y in line 450 is encountered, it goes back to Y=3 in the N=4 row, effectively "going back to where it left off". It eventually finds a safe spot at Y=7: Q                   Q                   Q                   Q                Although te above pattern will not result in eight queens, since we have saved the values of N and Y on the stack, we will eventually be able to "get back" to earlier columns. Ultimately, a valid solution will be found. The first valid solution is shown below: Q               Q       Q            Q   Q           Q           Q      Q        When this solution is eventually encountered by the program, N will be equal to 8. Note that in line 400, if N>=8, the program simply displays the board and returns (first pulling the last values of N and Y off of the stack). Note that the procedure does not stop there or clear the board. It will recurse back and try to find other similar solutions. Ultimately, it will find all 92 solutions to putting 8 queens on a chessboard such that none can attack another. There are a few important quirks to the 8 queens program: 1. It does not run on all BASIC interpreters. For example, GWBASIC will usually run out of memory. I'm using Extended Color Basic 1.0 with Disk Extended 1.1. 2. It is extremely slow. On a 0.9 MHz Color Computer, it takes several minutes just to find the first solution. 3. I haven't written a routine to record the solutions to the board. Once it finds the second solution, it forgets the first. This is easy to overcome by altering the "draw board" subroutine at line 490 (even something as simple as PRINT #-2 instead of PRINT would do the trick). Make sure you print the board to a tape/disk file or to the printer if you're planning on leaving the program running overnight to get all of the solutions. Don't print a CHR$(128) to a printer. It can have some interesting side effects on some printers. 4. The graphics aren't very good. There are other famous recursive routines that could be solved on the Color Computer. One is the method of printing out the contents of a binary tree in order. The logic for programming would be the same as in the chess example. Before the GOSUB to the recursive subroutine, push needed quantities onto a stack. Immediately before RETURNing from the subroutine, pull the same quantities off of it. W Aaron Banerjee 7620 Willow Point Falls Church, VA 22042  The ratio of one Fibonacci number over a preceding one approximates a "Golden Ratio" which occurs frequently in nature. For example the length of a leaf over it's breadth is a Golden Ratio. Even the dimensions of my credit card very closely approximate a Golden Ratio.  Cohen, N.H. "ADA as a Second Language". McGraw-Hill. 1986. Exercise 9.1 mely slow. On a 0.9 MHz Color Computer, it takes several minutes just to find the first solution. 3. I haven't written a routine to record the solutions to the board. Once it finds the second solution, it forgets the first. This is easy to overcome by altering the "draw board" subroutine at line 490 (even something as simple as PRINT #-2 instead of PRINT would do the trick). Make sure you print the board to a tape/disk file or to the printer if you'ABEWa@q T \]c| u<x<z<<<==2>4>   KMEY24_awAc>@oq  , T V X % '  acXZikacp|~ !!!!!!0!!!!HL9;8FNVv~ 3Hmv7@_k#5Dp|0C^q (Gk|& X 9";"g$i$%%%%!!!![%%%%%%%%%%%%%%%%%%%%%%%%%%%&&&& & & &&&&&&&&&&!&#&%&'&)&+&-&/&1&3&5&7&9&;&=&?&A&C&E&G&I&K&M&O&Q&S&U&W&Y&!:lc1  i 9 q GY&[']'(((((((()))) ) ) ))))))))) )")$)&)()*),).)0)2)4)6)8):)<)>)@)B)D)F)H)J)L)N)P)R)T)V)X)Z)\)^)`)b)d)f)h)j)l)n)p)r)t)v):lc1  i 9 q !!!Ev)x)z)|)~)))))g*i*l*n*p*r*t*v*x*z*|*~****************************************************!!:lc1  i 9 q G************+,,//W1Y1\1^1`1b1d1f1h1j1l1n1p1r1u1w1y1{1}11111111111111111111111111111111111!!!:lc1  i 9 q E11111111111111111111111)3+3.30323436383:3<3>3@3B3D3F3H3J3L3N3P3R3U3W3Y3[3]3_3a3c3e3g3i3k3m3o3q3s3u3w3y3|3~33333333!!:lc1  i 9 q G333333333333333333333333333444444444444444444444444445555 5 5 555555555!5#5%5'5!!:lc1  i 9 q G'5)5+5-5/515456585:5<5>5@5B5D5F5H5K5M5O5Q5S5U5X5Z5\5^5`5b5d5f5K6M6B7D777$8&888:::::u<w<z<|<<<<<=0>2>4>!!!!!!:lc1  i 9 q 9 F   <agaaaaag< !*3<Vj 4> %Y&v)*13'54>!"#$%&'()UTimes New Roman Symbol&Arial 1Courier1Courier 12cpi1Courier 10cpi<'''p'"h,ݑ,r,!S 9R!Recursive procedures for the CocoALEXANDER PRICEALEXANDER PRICE