[Tutor] fibonacci

[Jayprasad J. Hegde]

On Fri, Feb 14, 2003 at 03:40:16PM -0000, alan.gauld@bt.com wrote:
[ snip ] 

> > I would not recommend creating a second order (containing two 
> > recursive elements e.g. "fib (n - 1)" and  "fib (n - 2)" ) 
> I'm curious, why not?
> (Aside from performance maybe which is just as true with any 
> recursive solution.)
 ^^ not really. What you are saying would be true for most  calls which depend on only _one_ recursive element; this would have been perfectly acceptable. 
 
However, things are a bit different with the given "fib" definition 
in particular. 
If you analyse  the "fib" calls closely you'll  see that the recursion
is not  exactly linear i.e., every "fib"  call will generate  two more
"fib" calls and this will grow almost exponentially. 

Hence, for  "fib (4)" -- with  the base-case being  "fib (0)" and  "fib (1)"
-- you'll be making a total of 8 calls; for "fib (5)" it will be 14 calls; 
for "fib (6)" you'll get 24 calls; and so on.

Compare this with the typical recursive function, say recfun (x), where 
"recfun (5)" would possibly result in 4 more "recfun" calls and then return.

- JJH
-- 
The good die young -- because they see it's no use living if you've got
to be good.
		-- John Barrymore
(defun JJHdetails ()
  (format t "~&~A~&~A~&~A"
    "Jayprasad J Hegde, KBCS, NCST" "Gulmohar Cross
    Road 9, Juhu, Mumbai 400049." "tel: +91-22-26201606x373"))