projects:recurse.blk
Tutorial on Recursion
print Screen 0 not modified 0 \ Examples for lecture number eight. 11:18JWB02/28/86 1 \ Last change: Screen 001 17:03jwb03/24/87 2 3 4 Tutorial on Recursion. 5 6 7 8 9 10 11 12 13 14 15 Screen 1 not modified 0 \ A Tutorial Recursion in FORTH Programming. 1 \ I can remember, it seems like only yesterday, studying 2 \ arithmetic progressions in high school. I don't know why but 3 \ for some reason I hated them. We started of with a definition 4 \ something like the following: 5 6 \ Definition 5.0101 An arithmetic progression is a sequence in 7 \ which each term after the first is obtained by adding the same 8 \ fixed number, called the common difference, to the preceding 9 \ term. 10 11 \ I realise now what the problem was, and why I was bothered! 12 \ This is a recursive definiton. Apparently humans are supposed 13 \ to relate well to recursive definitions. But why do we call 14 \ this a recursive definition? It is because the next term of 15 \ the progression is defined in terms of the previous one. Screen 2 not modified 0 \ Here is what the definition is saying. 1 \ If d is the common difference, a fixed constant for any given 2 \ arithmetic progression then you can find the nth term by the 3 \ following formula: 4 \ A(n) = A(n-1) + d (n) and (n-1) are subscripts 5 \ where A(0) = a the 0th term ( some call it the 1st) 6 7 \ Example: if A(0) = a = 3 and d = 5 then 8 \ then: A(1) = A(0) + d = 3 + 5 = 8 9 \ A(2) = A(1) + d = 8 + 5 = 13 10 \ A(3) = A(2) + d = 13 + 5 = 18 11 \ And so on and so on adinfinitum! 12 \ But whats all this got to do with FORTH programming? 13 \ Well... we can write a FORTH program to find the nth term 14 \ of an arithmetic progression even though the only formula 15 \ I have given for the nth term is "recursive" Screen 3 not modified 0 \ Here is the algorithm: 1 \ To find A(n): 2 \ examine n: 3 \ IF ( n is not zero ) 4 \ call myself with argument (n-1) 5 \ and add d, the common difference to result. 6 \ ELSE ( n is equal to zero ) 7 \ then the answer is just 8 \ A(0) = a , the 0th term. 9 \ End of algorithm: 10 11 \ Implementing this algorithm in FORTH is going to present a 12 \ slight problem. If we call the procedure APN for nth term 13 \ of an arithmetic progression. 14 \ Then we are going to have to use the procedure 15 \ (word) APN in its own definition. Screen 4 not modified 0 \ FORTH program for computing the nth term 1 \ of an arithmetic progression: 2 VARIABLE A 3 A ! ( the 0th term ) 3 VARIABLE D 5 D ! ( the common difference ) 4 5 : APN ( n nth) 6 DUP IF ( n is not zero ) 7 1- APN D @ + 8 ELSE ( n is zero ) 9 DROP A @ 10 THEN ; 11 12 \ If you try to enter this you are in for a rude suprize. 13 \ FORTH does not like you using a definition in itself! 14 \ Depending on the FORTH system you are using the procedure 15 \ for getting a word to compile itself is different. Screen 5 not modified 0 \ If you are using a fig-FORTH or FORTH-79 1 \ and some FORTH-83 systems you would replace the word APN in 2 \ the middle of the definition with the word MYSELF or RECURSE 3 \ Check your system to see if you have these words. If you don't 4 \ here are their definitons. 5 6 : MYSELF LAST @ NAME> , ; IMMEDIATE 7 : RECURSE LAST @ NAME> , ; IMMEDIATE 8 9 \ You don't need both, either one will do. LAST is just a 10 \ variable which contains the name field address of the most 11 \ recently defined word. NAME> converts the name field address 12 \ into the compiliation address or cfa and the , compiles 13 \ the cfa into the dictionary. The definition must be immediate 14 \ so that MYSELF or RECURSE execute during compilation so as to 15 \ compile the word being defined ( APN in our example ) Screen 6 not modified 0 \ Here is how the definition would look using 1 \ MYSELF . I have added a line at the beginning of the word 2 \ definition and at the end of the word definition to monitor 3 \ the stack and status. Remove these lines when you understand 4 \ what is going on. 5 VARIABLE A 3 A ! ( the 0th term ) 6 VARIABLE D 5 D ! ( the common difference ) 7 8 : APN ( n nth) 9 CR ." Entering " .S 10 DUP IF ( n is not zero ) 11 1- MYSELF D @ + 12 ELSE ( n is zero ) 13 DROP A @ 14 THEN 15 CR ." Leaving " .S ; Screen 7 not modified 0 \ If you are using Laxen and Pery F83 for the PC 1 \ there is a different approach to making recursive definitions. 2 \ In L&P you can simply declare a word to be recursive using 3 \ the word RECURSIVE or course, and then you can use the word 4 \ you are defining in its own definition. Here is L&P version: 5 VARIABLE A 3 A ! ( the 0th term ) 6 VARIABLE D 5 D ! ( the common difference ) 7 8 : APN ( n nth) RECURSIVE 9 CR ." Entering " .S 10 DUP IF ( n is not zero ) 11 1- APN D @ + 12 ELSE ( n is zero ) 13 DROP A @ 14 THEN 15 CR ." Leaving " .S ; Screen 8 not modified 0 \ Teacher Hat On! Now here is your homework. 1 \ I didn't like the definition I was given for the geometric 2 \ progression any better than the one I was given for the 3 \ arithmetic progression ( you see it to is recursive). 4 \ Here it is: 5 \ Definition 14.2013 A geometric progression is a sequence in 6 \ which each term after the first is obtained by multiplying 7 \ the same fixed number, called the common ratio, by the 8 \ preceding term. 9 \ Your homework: Write a recursive definition to compute the 10 \ nth term of a geometric progression. Call the word GPN . 11 \ Use G(0) = A for the first term. and R for the common ratio. 12 \ With A = 3 and R = 2 your the geomtric progression would be: 13 14 \ 3, 6, 12, 24, 48, 96, etc 15 Screen 9 not modified 0 \ Hints on homework problem: 1 \ Here is the word algorithm for the geometric progression. 2 \ To find G(n): 3 \ examine n: 4 \ IF ( n is not zero ) 5 \ call myself with argument (n-1) 6 \ and multiply the result by r, the common ratio. 7 \ ELSE ( n is equal to zero ) 8 \ then the answer is just 9 \ G(0) = a , the 0th term. 10 \ End of algorithm: 11 \ The program would start as follows: 12 VARIABLE A 3 A ! ( The first term ) 13 VARIABLE R 2 R ! ( The common ratio ) 14 : GPN ( n nth) RECURSIVE ( if you are using L&P F83 ) 15 Opps, I just realized I'm doing your homework! Screen 10 not modified 0 \ More examples of recursive definitons. 1 \ Remove the lines at the begining and end of each definition 2 \ that print the stack once you understand what is going on. 3 \ FACTORIAL 4 \ Recursive definition: n! = n(n-1)! where 0! = 1 5 \ Examples: 5! = 5*4! 6 \ Algorithm: 7 \ To fine n!: 8 \ Examine n 9 \ IF ( n is not zero ) 10 \ call myself with n-1 11 \ multiply result by n 12 \ ELSE ( n is zero ) 13 \ return result of 1 14 \ THEN 15 \ End of n!; Screen 11 not modified 0 \ Program for n! 1 : FACTORIAL ( n n! ) RECURSIVE 2 CR ." Entering factorial" .S 3 DUP IF ( n is not zero ) 4 DUP 1- FACTORIAL * 5 ELSE ( n is zero ) 6 DROP 1 7 THEN 8 CR ." Leaving factorial" .S ; 9 10 \ If you try this with negative n you will be sorry! 11 \ Fix it so an error message is given if negative is on stack. 12 \ What is the largest factorial you can calculate with this 13 \ definition? 14 \ Implement FACTORIAL using double numbers. Hint: you need D* 15 \ If you don't have it is on the FORTH Board in Area 2 ! Screen 12 not modified 0 \ Power function 2^n 1 \ Definition: 2^n = 2*2^(n-1) if n=0 2^n = 1 2 \ Algorithm: 3 \ To find 2^n: 4 \ Examine n 5 \ IF ( n not zero) call myself with argument n-1 6 \ and multiply the result by 2 7 \ ELSE ( n is zero ) just return with 1 for the answer. 8 \ THEN End of 2^n; 9 \ Program: 10 : 2^n ( n 2^n ) RECURSIVE 11 CR ." Entering" .S 12 DUP 0> IF 1- 2^n 2* 13 ELSE DROP 1 14 THEN 15 CR ." Leaving " .S ; Screen 13 not modified 0 \ The famous Fibonacci numbers! 1 \ 0 1 1 2 3 5 8 13 21 34 etc 2 \ Definition: F(n) = F(n-1) + F(n-2) for n > 1 3 \ F(n) = n if n = 0 or 1 4 \ Wow! this one is doubly recursive. 5 \ Here is the program. You reconstruct the word algorithm. 6 : FIBONACCI ( n Fn ) RECURSIVE 7 CR ." entering" .S 8 DUP 0< ABORT" invalid argument" 9 DUP 1 > 10 IF DUP 1- FIBONACCI 11 SWAP 2- FIBONACCI + 12 ELSE ( nothing to do as we have a 1 or 0 ) 13 THEN 14 CR ." leaving " .S ; 15 Screen 14 not modified 0 \ Greatest common divisor 1 \ The greatest common divisor of two numbers a and b is the 2 \ largest number n that will divide into both a and b. 3 \ Here is the recursive definition, you figure out how it works 4 5 : GCD ( a b n ) RECURSIVE 6 CR ." Entering " .S 7 DUP IF SWAP OVER MOD GCD 8 ELSE DROP 9 THEN 10 CR ." Leaving " .S ; 11 12 13 14 15 Screen 15 not modified 0 \ Recursove Bubble Sort on the Stack. 1 2 \ BUBBLE does one pass. It is the recursive word! 3 : BUBBLE ( n n n ... m m m ... one pass ) RECURSIVE 4 CR ." ENTERING " .S 5 DEPTH 1 > 6 IF 2DUP < IF SWAP THEN 7 >R BUBBLE R> 8 THEN 9 CR ." LEAVING " .S ; 10 \ You can get rid of the entering and leaving . 11 \ To use: put any numbers on the stack and type SORT 12 : SORT ( n n n n ... m m m m ... sorted ) 13 DEPTH 1 > IF 14 DEPTH 1- 0 DO BUBBLE LOOP THEN ; 15 Screen 16 not modified 0 \ Directional Recursive Bubble Sort on the stack. 1 VARIABLE DIRECTION 2 : ASCENDING DIRECTION ON ; : DESCENDING DIRECTION OFF ; 3 : COMPARE DIRECTION @ IF < ELSE > THEN ; 4 5 : BUBBLE ( n n n ... m m m ... one pass ) RECURSIVE 6 CR ." ENTERING " .S 7 DEPTH 1 > 8 IF 2DUP COMPARE IF SWAP THEN 9 >R BUBBLE R> 10 THEN 11 CR ." LEAVING " .S ; 12 13 : SORT ( n n n n ... m m m m ... sorted ) 14 DEPTH 1 > IF 15 DEPTH 1- 0 DO BUBBLE LOOP THEN ; Screen 17 not modified 0 \ TOWERS-1 1 \ The Famous Towers of Hanoi by Peter Midnight. 2 \ From FORTH Dimensions Volume 2 Number 2. 3 \ Converted to Laxen and Perry F83 by Jack Brown. 4 \ The original author left out the stack comments and I don't 5 \ have time to put them in today. Send me a copy with them in! 6 : CLS ( -- -- ) 27 EMIT ." [2J" ; \ Clear screen. 7 CODE AT ( row col -- ) \ position cursor. 8 AX POP DX POP AL DH MOV BH BH XOR 2 # AH MOV 16 INT 9 NEXT END-CODE 10 \ : 4DUP ( a b c d a b c d a b c d ) 2OVER 2OVER ; 11 12 CONSTANT NMAX VARIABLE (N) NMAX (N) ! 12 : N ( -- n ) (N) @ ; \ fetch value of n. 13 61 CONSTANT COLOR 14 VARIABLE HFO 3 HFO ! 15 VARIABLE RING N ALLOT Screen 18 not modified 0 \ TOWERS-2 1 2 : DELAY ( n -- ) 3 0 DO 17 0 DO 127 127 * DROP LOOP LOOP ; 4 : POS ( n n' ) 5 N 2* 1+ * N + ; 6 : HALFD ( char size -- ) 7 0 DO DUP EMIT LOOP DROP ; 8 : <DISP> ( row char size -- ) 9 2DUP HALFD ROT 3 < IF BL ELSE ASCII H 10 THEN EMIT HALFD ; 11 : DISPLAY 12 SWAP >R -ROT OVER - R@ AT 13 R> -ROT <DISP> ; 14 15 Screen 19 not modified 0 \ TOWERS-3 1 2 : PRESENCE ( n flag ) 3 RING + C@ = ; 4 : LINE 5 4 SWAP N 0 DO DUP I PRESENCE 1+ 6 ROT + SWAP LOOP DROP ; 7 : RAISE 8 DUP POS SWAP LINE 2 SWAP 9 DO 2DUP I BL DISPLAY 2DUP I 1- COLOR DISPLAY 10 -1 +LOOP 2DROP ; 11 : LOWER 12 DUP POS SWAP LINE 1+ 2 13 DO 2DUP I 1- BL DISPLAY 2DUP I COLOR DISPLAY 14 LOOP 2DROP ; 15 Screen 20 not modified 0 \ TOWERS-4 1 : MOVELEFT 2 POS SWAP POS 1- DO DUP I 1+ 1 BL DISPLAY 3 DUP I 1 COLOR DISPLAY -1 +LOOP DROP ; 4 5 : MOVERIGHT 6 POS 1+ SWAP POS 1+ DO DUP I 1- 1 BL DISPLAY 7 DUP I 1 COLOR DISPLAY LOOP DROP ; 8 9 : TRAVERS 10 2DUP > IF MOVELEFT ELSE MOVERIGHT THEN ; 11 12 : MOVE1 13 KEY? IF 0 16 AT ABORT THEN 14 -ROT 2DUP RAISE >R 2DUP R> ROT TRAVERS 15 2DUP RING + 1- C! SWAP LOWER ; Screen 21 not modified 0 \ TOWERS-5 1 : MULTIMOV RECURSIVE 2 3 PICK 1 = IF DROP MOVE1 ELSE 3 >R >R SWAP 1- SWAP R> R> 4DUP SWAP MULTIMOV 4 4DUP DROP ROT 1+ -ROT MOVE1 5 -ROT SWAP MULTIMOV THEN ; 6 : MAKETOWER 7 POS 4 N + 3 DO DUP I AT 79 EMIT LOOP DROP ; 8 : MAKEBASE 9 0 N 4 + AT N 6 * 3 + 0 DO 77 EMIT LOOP ; 10 : MAKERING 11 2DUP RING + 1- C! SWAP LOWER ; 12 : SETUP 13 CLS N 1+ 0 DO 1 RING I + C! LOOP 3 0 DO I 14 MAKETOWER LOOP MAKEBASE 1 N DO 0 I MAKERING -1 +LOOP ; 15 Screen 22 not modified 0 \ TOWERS-6 1 \ Values of n larger than 7 take a fair amount of time. 2 : TOWERS ( n -- ) 3 1 MAX NMAX MIN (N) ! 4 SETUP N 2 0 1 BEGIN 5 OVER POS N 4 + AT N 0 6 DO BEEP 5 DELAY LOOP 7 ROT 4DUP MULTIMOV 8 HFO @ 1- DUP HFO ! UNTIL 9 2DROP 2DROP 10 0 0 AT 11 N 0 DO BEEP 5 DELAY LOOP ; 12 13 : HANOI 7 TOWERS ; 14 15
projects/recurse.blk.txt · Zuletzt geändert: 2013-06-06 21:27 von 127.0.0.1