Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!linus!philabs!cmcl2!harvard!think!mit-eddie!genrad!decvax!ittatc!dcdwest!sdcsvax!sdcrdcf!randvax!florman
From: florman@randvax.UUCP (Bruce Florman)
Newsgroups: net.lang.forth
Subject: Re: Recursion forth
Message-ID: <280@randvax.UUCP>
Date: Mon, 5-May-86 17:15:33 EDT
Article-I.D.: randvax.280
Posted: Mon May  5 17:15:33 1986
Date-Received: Sat, 10-May-86 12:57:38 EDT
References: <1854@mtgzz.UUCP>
Organization: Rand Corp., Santa Monica
Lines: 67

> 
> 	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