Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!mhuxn!ihnp4!houxm!mtuxo!mtgzz!bds
From: bds@mtgzz.UUCP (b.d.szablak)
Newsgroups: net.lang.forth
Subject: Recursion forth
Message-ID: <1854@mtgzz.UUCP>
Date: Thu, 1-May-86 14:24:50 EDT
Article-I.D.: mtgzz.1854
Posted: Thu May  1 14:24:50 1986
Date-Received: Sat, 3-May-86 18:47:49 EDT
Organization: AT&T Information Systems Labs, Holmdel NJ
Lines: 32


	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
	;