[Tutor] fibonacci

[alan.gauld@bt.com]

> >>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.)
> >  
> >
> This definitely has to be seen more differentiating ... (YKWIM?)
> 
> fib1(24) needs 24 recursive calls (because this version is 
> eqivalent to a simple for-loop),
> while fib2(24) needs more than 150000 recursive calls, the number 
> of recursive calls growing (approx) geometrically with n.

OK, so the reason is performance which is nearly always bad 
compared to iterative solutions (unless your language supports 
tail end recursion.) Plus the fact that with 2 recursions you 
get geometric progression which is rather like saying you should 
never use nested loops... there's no good reason other than 
performance.

> So it certainly will be definitly *impossible* to compute fib2(100), 

Using Python certainly, if we had stackless Python it might very 
well be possible since, I believe, it doesn't suffer Pythons 
restrictions on recursion. OTOH it would take an awful long time!

> Convincing?

I knew it was slow (I'd already tried fib(50) before posting!)
The bit I was actually trying to highlight when I posted my solution 
wasn't the recursive bit at all but the rather clumsy termination test 
that Alfred was originally using.

Alan G.