Re: [Tinycc-devel] fib.c

[Dave Dodge]

On Thu, Mar 15, 2007 at 04:38:07PM -0700, Laszlo Hars wrote:
> If you want to demonstrate recursive calls, here is an alternative,
> which saves already computed results, and so the number of recursive
> calls is never more than n:

Aside: if you don't need the cached values for later runs of fib(n),
or you want to avoid static data for thread-safety, you can do even
better.  Here's an O(n) recursive technique with no value cache.  Also
note that it uses tail recursion, so it can be compiled (if the
compiler recognizes it) to run to any n with only one stack frame:

static unsigned long long fibstep(
    unsigned int const remaining,
    unsigned long long const prev,
    unsigned long long const prevprev)
{
    unsigned long long const fibnext = prev + prevprev;
    if (fibnext < prev)
        return 0; /* overflow */
    if (remaining == 0)
        return fibnext;
    else
        return fibstep(remaining - 1,fibnext,prev);
}

unsigned long long fib(unsigned int const n)
{
    switch (n)
    {
        case 0: return 0;
        case 1: return 1;
        default: return fibstep(n - 2,1,0);
    }
}

                                                  -Dave Dodge