Forth-eV Wiki

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