Re: To understand recursion, one must first understand recursion (was Re: apple iie overheat question)

[Scott Hemphill <hemphill@hemphills.net>]

"Hidehiko Ogata" <hog@aqu.candybar.ne.jp> writes:

> Scott Hemphill wrote:
> 
> > You could still use recursion, but tame it a little bit by not recalculating
> > a value that has already been calculated:
> >
> >   #define MAXTABLE 2000  // or whatever
> >   double F(int n)
> >   {
> >     static double fibtable[MAXTABLE] = {0, 1};
> >     static int maxfib = 1;
> >     if (n < 0 || n >= MAXTABLE) return 0;  // catch error
> >     if (n > maxfib) {
> >       fibtable[n] = F(n-1) + F(n-2);
> >       maxfib = n;
> >     }
> >     return fibtable[n];
> >   }
> 
> Hmm, shouldn't today's compilers be smart enough to detect and
> optimize tail-recursion?  As in:
> 
>     double fib(int n)
>     {
>         return fib_iter(1, 0, n);
>     }
> 
>     double fib_iter(double old, double older, int count)
>     {
>         return count ? fib_iter(old + older, old, --count) : older;
>     }
> 
> (Excuse me for butting in... it's an irresistible subject for
> a scheme fan ;)

I don't mind at all.  The topic was already straying from the Apple ][.
GNU cc doesn't do this optimization.  I'll leave the topic of whether it
should to others.

I was hoping that somebody would bite on my direct calculation for the
Fibonacci sequence, wondering where my "magic constants" came from, and
why it works.  I guess most people either already know, or don't care.

Scott
-- 
Scott Hemphill	hemphill@alumni.caltech.edu
"This isn't flying.  This is falling, with style."  -- Buzz Lightyear