home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / forth / compiler / fpc / tutor / l7p170 < prev    next >
Text File  |  1990-07-15  |  3KB  |  90 lines
  1.  
  2.        ╔═════════════════════════════════════════════════════╗
  3.        ║  Lesson 7 Part 170 F-PC 3.5 Tutorial by Jack Brown  ║
  4.        ╚═════════════════════════════════════════════════════╝
  5.  
  6.  
  7. More examples of recursive definitions. Remove the lines at the beginning
  8. and end of each definition that print the stack once you understand what
  9. is going on.
  10.              ┌─────────────────────────────────────┐
  11.              │  Recursive Definition of Factorial  │
  12.              └─────────────────────────────────────┘
  13. FACTORIAL
  14. Recursive definition:  n! = n(n-1)!   where 0! = 1
  15. Examples:  5! = 5*4!
  16. Algorithm:
  17. To fine n!:
  18.        Examine n
  19.        IF ( n is not zero )
  20.           call myself with n-1
  21.           multiply result by n
  22.        ELSE ( n is zero )
  23.           return result of 1
  24.        THEN
  25. End of n!;
  26.  
  27. Program for n!
  28.  : FACTORIAL   ( n -- n! ) RECURSIVE
  29.    CR ." Entering factorial" .S
  30.    DUP    IF   ( n is not zero )
  31.                DUP 1-  FACTORIAL  *
  32.           ELSE ( n is zero )
  33.                DROP 1
  34.           THEN
  35.    CR ." Leaving  factorial" .S ; 
  36.  
  37. If you try this with negative n you will be sorry! Fix it so an error
  38. message is given if negative is on stack. What is the largest factorial
  39. you can calculate with this definition? Implement FACTORIAL using double
  40. numbers.  Hint: you need D* If you don't have it is on the FORTH Board
  41. in Area 2 !
  42.  
  43.            ┌──────────────────────────────────────────┐
  44.            │  Recursive Definition of Power Function  │
  45.            └──────────────────────────────────────────┘
  46.  
  47. Power function  2^n
  48. Definition:   2^n = 2*2^(n-1)     if n=0   2^n = 1
  49. Algorithm:
  50. To find 2^n:
  51.        Examine n
  52.        IF ( n not zero) call myself with argument n-1
  53.           and multiply the result by 2
  54.        ELSE ( n is zero ) just return with 1 for the answer.
  55.        THEN  End of 2^n;
  56.  
  57. Program:
  58.     : 2^n   ( n -- 2^n )  RECURSIVE
  59.           CR ." Entering" .S
  60.           DUP 0> IF   1-  2^n  2*
  61.                  ELSE DROP 1
  62.                  THEN
  63.           CR ." Leaving " .S ;
  64.   
  65.            ┌─────────────────────────────────────────────┐
  66.            │  Recursive Definition of Fibonacci Numbers  │
  67.            └─────────────────────────────────────────────┘
  68.  
  69. The famous Fibonacci numbers!
  70.  0 1 1 2 3 5 8 13 21 34 etc
  71. Definition:  F(n) = F(n-1) + F(n-2)   for n > 1
  72.               F(n) = n   if n = 0 or 1
  73. Wow! this one is doubly recursive.
  74.  
  75. Here is the program.  You reconstruct the word algorithm.
  76.  : FIBONACCI ( n   Fn  )  RECURSIVE
  77.        CR  ." entering" .S
  78.        DUP 0< ABORT" invalid argument"
  79.        DUP 1 >
  80.        IF    DUP  1-  FIBONACCI
  81.              SWAP 2-  FIBONACCI  +
  82.        ELSE  ( nothing to do as we have a 1 or 0 )
  83.        THEN
  84.        CR ." leaving " .S ;
  85.   
  86. ┌───────────────────────────────────┐
  87. │  Please Move to Lesson 7 Part 180 │
  88. └───────────────────────────────────┘
  89.  
  90.