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

[salfter@salfter.diespammersdie.dyndns.org (Scott Alfter)]

-----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.

  _/_
 / v \ Scott Alfter (remove the obvious to send mail)
(IIGS( http://alfter.us/            Top-posting!
 \_^_/ rm -rf /bin/laden            >What's the most annoying thing on Usenet?

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (GNU/Linux)

iD8DBQFCe8nvVgTKos01OwkRAnAeAKCLAvV6IdAz3NpVVjWS5gWfmizxIgCfck6T
eXnkj/eqfxxyoxN5JyUBSPY=
=ZO3X
-----END PGP SIGNATURE-----