Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!bellcore!decvax!ittatc!dcdwest!sdcsvax!sdcc6!sdcc3!ma168x
From: ma168x@sdcc3.UUCP (John Wavrik)
Newsgroups: net.lang.forth
Subject: Forth and recursion
Message-ID: <3282@sdcc3.UUCP>
Date: Sat, 3-May-86 15:07:41 EDT
Article-I.D.: sdcc3.3282
Posted: Sat May  3 15:07:41 1986
Date-Received: Tue, 6-May-86 05:04:09 EDT
Organization: U.C. San Diego, Academic Computer Center
Lines: 64
Keywords: recursion Fibonacci


Re:  Posting on recursive computation  (B.D. Szablak)

  Fibonacci numbers provide an excellent example of a situation
in which iteration should be used rather than recursion.
              FIB(n) = FIB(n-1) + FIB(n-2)
       with   FIB(0) = FIB(1) = 1
It is easy to see that the number of additions required grows
like n if iteration is used and like FIB(n) if recursion is used

   A recursive computation of FIB(20) requires 10945 additions
while an iterative computation only requires 19 additions.

ITERATION:
For Fibonacci numbers, let F be a variable holding the most
recent Fibonacci number and F- the one before.

   : FIB  ( iterative )   DUP 2 <
         IF        DROP 1            ( boundary value)
         ELSE   1 F- !  1 F !
                1 DO    F- @  F @     DUP F- !  ( update F-)
                        +                 F  !  ( update F )
                  LOOP   F @
         THEN  ;

RECURSION:
Forth is implemented deliberately to prevent the word currently
being defined from being found in a dictionary search.
There are three major techniques used for recursion in Forth:
     1.  Defeat the (system dependent) method used to
         prevent self-reference [e.g. toggle the SMUDGE bit].
     2.  Provide a word (usually called MYSELF) which compiles
         the code address of the current word.
     3.  Use execution vectors.

Here is an example using approach #2:
  : FIB  ( recursive )  DUP 2 <
         IF    DROP 1
         ELSE  DUP 1-  MYSELF  SWAP  2-  MYSELF +  THEN  ;

The FIG-Forth definition of MYSELF is
  :  MYSELF  LATEST  PFA CFA ,  ; IMMEDIATE
   ( where : LATEST   CURRENT @ @  ;  )

Recursion is not a major control mechanism in Forth. It should
be noted that most Forth systems have relatively small return
stacks -- limiting the depth of recursion to 100 levels or less.
This is adequate for isolated situations (e.g. quicksort) where
recursion is justified.
   Forth is a very interesting language: the system is open and
the method of implementation simple. It soon becomes evident
that it would be very easy to provide for all kinds of things:
to use self-modifying code, to define a GOTO word to jump from
one word to the middle of another, etc.  Support for these is
not provided and the possibility not mentioned in books. There
is a good reason:  Forth was developed when efficiency and the
ability to write maintainable code were important.
   Recursion is borderline. It is often not efficient but can
sometimes be useful. Many Forth systems provide it and it can be
easily added to others.
                                      John J Wavrik
                                      Dept of Math
                                      Univ of Calif - San Diego
...ucbvax!sdcsvax!sdcc3!ma168x