Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!allegra!mit-eddie!genrad!panda!husc6!harvard!topaz!bentley!kwh
From: kwh@bentley.UUCP (KW Heuer)
Newsgroups: net.lang.forth
Subject: Re: Recursion forth
Message-ID: <789@bentley.UUCP>
Date: Sun, 4-May-86 19:07:05 EDT
Article-I.D.: bentley.789
Posted: Sun May  4 19:07:05 1986
Date-Received: Tue, 6-May-86 06:02:37 EDT
References: <1854@mtgzz.UUCP>
Organization: AT&T Bell Laboratories, Liberty Corner
Lines: 21

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

My own solution is to use a version of forth that supports recursion.  (Well,
it supports direct recursion, anyway.  Someday I'll add indirect recursion.)

>I eventually came up with an iterative solution ...

If your goal is to learn how to simulate recursion, then what you wrote is
probably as good as anything.

But if you really want a fib function, the function
	: fib 0 1 rot 1 do dup rot + loop swap drop ;
is simpler and faster (linear time as opposed to exponential), and won't
overflow the stack.

(There's also an O(log n) algorithm, but I won't bore you with the details
unless you're interested.)

Karl W. Z. Heuer (ihnp4!bentley!kwh), The Walking Lint