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

[Scott Hemphill <hemphill@hemphills.net>]

salfter@salfter.diespammersdie.dyndns.org (Scott Alfter) writes:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> In article <cvPee.38$r04.117@news.oracle.com>,
> Martin Doherty  <martin.doherty@undisclosed.com> wrote:
> >In 1983 I wrote an Apple Pascal program to read a list of words and try 
> >to construct crosswords, scoring the results on how many words were 
> >included (the longer the better). It was an interesting exercise in 
> >recursive programming, but I was horrified at how slowly the results 
> >trickled out.
> 
> One assignment I was given in an introductory computer-science course was to
> write a program to generate the Fibonacci sequence.  Since each number in
> the sequence is the sum of the previous two numbers (with the first two
> being defined as 1), I had a brain-fart that said a recursive function F(n)
> to find the nth number in the sequence would be cool:
> 
> double F(int n)
> {
>   if (n<3)
>     return 1;
>   else
>     return F(n-1)+F(n-2);
> }
> 
> (F() returns double instead of int because the Fibonacci sequence rapidly
> causes int to overflow on 32-bit hardware.  I think the course was long
> enough ago that it would've used Pascal instead of C, but that's an
> implementation detail.)
> 
> This proved to be a demonstration of the principle that a little bit of
> knowledge can be dangerous. :-)
> 
> For small values of n, it worked well enough.  For values up above 100 or
> so, it quickly ground to a crawl.  Whether I ran it on a Sun SPARCstation 1,
> a NeXTcube, or the Convex supercomputer across the hall from the lab that
> they let us play with, it'd hit a wall in performance somewhere.
> 
> Not having any experience at the time with runtime analysis or any real
> knowledge of how things get done under the hood, I hadn't figured on the
> exponential growth of the stack space (and also of runtime) required to
> evaluate F(n) for even moderately large values of n.
> 
> The instructor dropped a hint that an iterative approach would be better:
> 
> double F(int n)
> {
>   double n1=0;
>   double n2=0;
>   double r=0
>   int i;
> 
>   for (i=1; i<=n; i++)
>   {
>     r=n1+n2;
>     if (r==0)
>       r=1;
>     n2=n1;
>     n1=r;
>   }
>   return r;
> }
> 
> It doesn't look as nice, but it ran much faster.

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];
  }

Or, you could compute the answer directly, without recursion or iteration:

  #include <math.h>
  double F(int n)
  {
    const double c1 = 0.48121182505960344749775891342437; // magic constants 
    const double c2 = 0.80471895621705018730037966661309; // :-)
  // let n < 0 fall through.  function will return zero
    return floor(0.5 + exp(n*c1-c2));
  }

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