Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Posting-Version: version B 2.10.2 9/5/84; site yale.ARPA Path: utzoo!watmath!clyde!burl!ulysses!bellcore!decvax!yale!makdisi From: makdisi@yale.ARPA (Makdisi) Newsgroups: net.lang.forth Subject: Re: Recursion forth Message-ID: <2441@yale.ARPA> Date: Fri, 2-May-86 16:43:57 EDT Article-I.D.: yale.2441 Posted: Fri May 2 16:43:57 1986 Date-Received: Sun, 4-May-86 06:21:37 EDT References: <1854@mtgzz.UUCP> Reply-To: makdisi@yale-cheops.UUCP (Kamal Khuri-Makdisi) Organization: Yale University CS Dept., New Haven CT Lines: 78 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