// fib.cpp - one iterative and two recursive implementations of the Fibonacci function;
//           recall that f_0 = 0, f_1 = 1 and f_n = f_{n-1} + f_{n-2} for n > 1

#include <iostream>
using namespace std;

// straightforward iteratively implemented Fibonacci function; 
// run-time: O(n)
unsigned long
ifib( unsigned n )
{
   unsigned long pp = 0, p = 1;
   
   while ( n-- > 0 )
   {
      unsigned long t = pp;
      pp = p;
      p  = p+t;
   }
   
   return pp;
}


// simple recursively implemented Fibonacci function; highly inefficient, exponential
// run-time: O((phi^n)/sqrt(5)), where phi = (1+sqrt(5))/2 = 1.618..., or just 
//           O(2^n)  (a less tight, but simpler bound)
unsigned long
rfib( unsigned n )
{
   if ( n <= 1 )
      return (unsigned long) n;
   
   return rfib( n-1 ) + rfib( n-2 );
}


// the following function pair provides a fast recursive Fibonacci function);
// run-time: O(n)
unsigned long
aux_frfib( unsigned n, unsigned long pp, unsigned long p )
{
   if ( n == 0 )
      return pp;

   return aux_frfib( n-1, p, p+pp );
}

unsigned long
frfib( unsigned n )
{
   return aux_frfib( n, 0L, 1L );
}


int
main()
{
   cout <<  "ifib( 40 ) = " <<  ifib( 40 ) << endl;
   cout << "frfib( 40 ) = " << frfib( 40 ) << endl;
   cout <<  "rfib( 40 ) = " <<  rfib( 40 ) << endl;
   
   return 0;
}