[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Tinycc-devel] fib.c

From: Dave Dodge
Subject: Re: [Tinycc-devel] fib.c
Date: Fri, 16 Mar 2007 02:00:57 -0500
User-agent: Mutt/1.5.12-2006-07-14

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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]