Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

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