http://www.velocityreviews.com/forums/(E-Mail Removed) (Michael Wojcik) writes:

> In article <(E-Mail Removed)>, Eric Sosman <(E-Mail Removed)> writes:

> > Peteris Krumins wrote:

> > >

> > > #include <stdio.h>

> > >

> > > unsigned fib(unsigned n) {

> > > return n <= 2 ? 1 : fib(n - 1) + fib(n - 2);

> > > }

> > >

> > > int main(void) { printf("fib(17) is: %d\n", fib(17)); return 0; }

> >

> > Somebody always proposes this solution, but it's a

> > poor one. Try it with fib(47), say, and tell us how

> > long it takes. Hint: You won't need a high-precision

> > timer.

>

> Well, there's always this one (with error checking left as an

> exercise for the reader):

>

> /***

> prev2 and prev are the two immediately preceeding values in the

> series; prev2 is F(n-2) and prev is F(n).

> pos is the current position in the series.

> want is the position we're looking for.

> ***/

>

> unsigned fib_cps(unsigned prev2, unsigned prev, unsigned pos, unsigned want)

> {

> if (want <= 2) return 1;

> if (pos == want) return prev2 + prev;

> return fib_r(prev, prev2 + prev, pos + 1, want);

> }

>

> unsigned fib(n)

> {

> return fib_cps(1, 1, 3, n);

> }
(Of course you meant fib_cps rather than fib_r in the first function.)

Just for my own enjoyment:

unsigned

fib3( unsigned n, unsigned a, unsigned b ){

return n == 0 ? b : fib3( n-1, b, a+b );

}

unsigned

fib( unsigned n ){

return fib3( n, 1, 0 );

}

This definition yields fib(0) == 0, as the Fibonacci numbers are

usually defined.