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

["Hidehiko Ogata" <hog@aqu.candybar.ne.jp>]

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 ;)
-- 
  //  }{idehiko ()gata  "I hope I didn't hurt you too much
\X/    Amiga since '86   when I killed you..." - Elmer Fudd

bekkoame is a classic Japanese candybar.