gforth-tutorial/14-recursion.fth

1 0 / . \ "Floating-point unidentified fault" in Gforth on some platforms

\ Change `/` to throw an expection, if the divisor is 0,
\ otherwise continue with normal division.

: / ( n1 n2 -- n )
  dup 0= if
    \ report division by zero
    -10 throw
    endif
    \ Use original `/` version.
    /
    ;

1 0 /

\ Here is a recursive implementation of factorial using
\ `recurse`:

: factorial ( n -- n! )
  dup 0> if
    \ Create a new factor, reduced by 1.
    dup 1-
    recurse
    \ When the calls return, do a multiplication for each
    \ iteration.
    *
  \ If the number on top of the stack is zero, drop it.
  else
    drop 1
  then ;

\ Apparently `recurse` works simply by calling the function
\ again and one has to make sure, that the stack is in the
\ correct state, so that recurring works.

8 factorial .

\ However, unfortunately there can be a stack overflow, if
\ the recursion is too deep:

1000 factorial .

\ Also unfortunately integer numbers overflow between 20!
\ and 21!:

20 factorial .
20 factorial . 2432902008176640000  ok
21 factorial .
21 factorial . -4249290049419214848  ok

\ Assignment: Implement Fibonacci using recursion.

\ Note: This is a naive implementation.

: fibonacci ( n -- n )
  \ The nth part of the calculation is not the number n
  \ itself. For example 1 1 2 3 5 8 ... the 8 is not the 8th
  \ Fibonacci number.
  \ Fibonacci of 2 an 1 is 1:
  \ 1 1 2 3 5 8 ...
  \ ^ ^

  \ If n is still greater than 2, we use the usual formula
  \ for recursively calculating Fibonacci numbers.
  dup 2 >
  if
    \ Put the number reduced by 1 on the stack and put the
    \ number reduced by 2 on the stack. The order does not
    \ really matter, since they will only be the basis for
    \ recursive calls and the results of those recursive
    \ calls will be added, and order does not matter for
    \ addition of integers.
    dup 1 -
    swap
    2 -
    \ Calculate for n-2.
    recurse
    \ Swap the results to the 2. position on the stack, so
    \ that n-1 can be used for another recursive call.
    swap
    \ Calculate for n-1.
    recurse
    \ Add them both up.
    +
  \ Otherwise we hit the base case, which is returning 1.
  else
    \ Replace numbers, which are not > 2 with 1.
    drop 1
  then
  ;