# Forth-eV Wiki

### Webseiten-Werkzeuge

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 (Externe Bearbeitung)

### Seiten-Werkzeuge 