🚀 go-pugleaf

Summary:
Expires:
Sender:
Followup-To:
Distribution:
Keywords:

In article <1854@mtgzz.UUCP> bds@mtgzz.UUCP (b.d.szablak) writes:
>
>       I would appreciate it if someone well versed in forth programming
>could give this novice hints on coding recursive algorthims (the two Forth
>texts I have manage to avoid this topic). It seems the very first word that
>I (in all innocence) attempted to define was to evaluate the fibinocci
>function (in C):
>
>       fib(n)
>       {
>               if( n==1 || n==2 ) return 1;
>               return fib(n-1) + fib(n-2);
>       }
>
>I eventually came up with an iterative solution after spending more time
>than I would have liked so instructive comments on this would also be
>appreciated:
> [ ... long and confusing definition follows ... ]

Here's a simple way to find the nth Fibonacci number (a trick I learnt on my
cousin's programmable calculator, a TI58):

    : fib                       ( n1 -- n2, the n1th Fibonacci number )
	 0 1                    ( Stack is initially fib[0] fib[-1] )
	 rot 0 do               ( repeat n1 times )
	    over + swap         ( fib[i] fib[i-1] --becomes--> fib[i+1] fib[i] )
	 loop                   ( at end of loop, stack is fib[n1] fib[n1-1] )
	 drop                   ( leave fib[n1] on the stack )
    ;

or, more succinctly,
    : fib   0 1  rot 0 do  over + swap  loop drop ;

You don't want to do things like finding the nth fibonacci number recursively,
since recursively defining fib(n) = fib(n-1) + fib(n-2) on a non-psychic
computer makes the computer call fib many more times than is needed.  I.e. a
call to fib(5) makes the computer call fib(4) and fib(3), which make the
computer call fib(3), fib(2), fib(2), and fib(1).  The remaining fib(3) calls
fib(2) and fib(1).  Thus we've called fib(1) twice, fib(2) three times, and
fib(4) twice, even though we only needed to call each of those once.  Recursion
is not advisable in such cases (where a recursive procedure calls itself more
times than it needs to get the same result).  You can often be better off
writing something iterative.

Recursion is useful for algorithms that look ugly in iterative form, but can be
expressed cleanly and elegantly in recursive form.  An example is

	Number of nodes in an empty tree = 0
	Number of nodes in a non-empty tree =
		Number of nodes in the left subtree
	      + Number of nodes in the right subtree
	      + 1 (the root of the tree)

The idea here is also that the algorithm only "visits" each node in the tree
once.  It does not calculate the number of nodes in a given tree twice (unless
some parts of the tree are shared).

Regarding recursion in forth:  Brodie makes no mention of it in either of the
two books of his that I've read (_Starting Forth_ and _Thinking Forth_).  I've
heard of a forth implementation somewhere that allowed a word to call itself
with the special word MYSELF (anyone know where that is?).  The only way I can
think of to do recursion in forth is as follows:

	0 variable fib-addr
      : fib   fib-addr @ execute ;
      : fib-recurse   dup 3 < if  drop 1
			else  dup 1- fib  swap 2- fib + then ;
	' fib-recurse  fib-addr !

(Although, I repeat, I wouldn't calculate fibonacci numbers recursively except
for demonstrative or teaching purposes.)

Hope this helps!
				- K K-M   "Disclaimers galore"
-- 
Kamal Khuri-Makdisi (makdisi@yale.ARPA)		...!ihnp4!hsi!yale!makdisi
		    (makdisi@yalecs.BITNET)	   ...!decvax!yale!makdisi
      LAMAKDISIDKAMAL         LAMAKDISIDKAMAL         LAMAKDISIDKAMAL