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