🚀 go-pugleaf

> 
> 	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:
> 	: fib ( n1 -- n2 )  \ fibinocci value of n1
> 	   -1 swap 0 swap   \ stack: pending calcs., answer, current calc.
> 	   begin  dup 0>    \ do until current calc is <= 0
>            while  dup 1 =   \ fib 1 is 1
> 		  if     +  \ add fib 1 to answer
> 		  	 swap      \ next pending calc -> current calc.
> 		  else   dup 2 =   \ fib 2 is 1
> 			 if     drop 1+ \ add fib 2 to answer
> 				swap    \ next pending calc -> current calc.
> 			 else   1- tuck \ fib(n-1) is a pending calc.
> 				1-      \ fib(n-2) is current calc.
> 			 then
> 		  then
> 	   repeat
> 	   drop \ leave answer on top of stack - all pending calcs done
> 	;

    I'm not really "someone well versed in forth programming" as I've only
been doing it for about 3 weeks, but I'll risk ridicule and humiliation and
throw my 2 cents in.  I'm using a FORTH implementation called MACH 1 (on an
Apple Macintosh) which allows named input parameters.  The manual gives the
following example:

	: FIB RECURSIVE { num }
	   num 2 <
	   IF
		1
	   ELSE
		num 1- FIB
		num 2- FIB +
	   THEN ;

Without the named input parameters, the following modification does the
same computation:

	: FIB RECURSIVE ( n1 -- n2 )
	   DUP 2 <
	   IF
		DROP 1
	   ELSE
		DUP 1- FIB
		SWAP 2- FIB +
	   THEN ;

I'm not sure if the word RECURSIVE is in the 83 standard or not.  In MACH 1
it's required for a definition to reference itself.
    While not a full treatment of the subject, maybe this example helps to
shed some light on the subject.

				Bruce Florman
				florman%gnu@rand-unix.ARPA