#include /* Fibonacci Formal Definition: F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2) */ // templatized templatestruct Fibonacci{ static const uint64_t result = Fibonacci::result + Fibonacci::result ; }; template<>struct Fibonacci<0>{ static const uint64_t result = 0; }; template<>struct Fibonacci<1>{ static const uint64_t result = 1; }; // recursive uint64_t rFibonacci( uint64_t n ){ if ( n < 2 ) return n; return rFibonacci( n - 1 ) + rFibonacci( n - 2 ); } // loop // series #include std::vector getFibonacciSerie( uint64_t n ){ std::vector serie = {0,1}; for ( uint64_t i = 2 ; i <= n ; ++i ) serie.push_back( serie[ i - 1 ] + serie[ i - 2 ] ); return serie ; } // get value uint64_t getFibonacci( uint64_t n ){ return getFibonacciSerie( n )[ n ] ; } #include #include void printCompare( std::vector table ){ std::cout << " * * Fibonacci(n) result table loop vs recursion * *\n" << "input" << std::setw(14) << std::right << "loop" << std::setw(11) << std::right << "rec\n"; for ( uint64_t i = 0 ; i < table.size() ; ++i ){ std::cout << "F(" << std::setw(3) << std::right << i << ") : " << std::setw(10) << std::right << table[ i ] << std::setw(10) << std::right << rFibonacci( i ) << "\n"; } } using namespace std; int main() { cout << "Fibonacci(30)\n" << " * compile time<> : " << Fibonacci<30>::result << "\n * runtime recursion : " << rFibonacci(30) << "\n * runtime loop : " << getFibonacci(30) << endl << endl; cout << "Loop uses a continer to add elements from previous making it more simple and optimized\nFor example :\nF(80) : " << getFibonacci( 80 ) << endl << endl; printCompare( getFibonacciSerie( 20 ) ); return 0; }

Algorithms [Jhon Wells] Fibonacci