#include /* Hofstadter's Q sequence Formal Definition: Q(1) = Q(2) = 1 Q(n) = Q(n-Q(n-1)) + Q(n-Q(n-2)) */ // templatized templatestruct HofQ{ static const uint64_t result = HofQ::result>::result + HofQ::result>::result ; }; template<>struct HofQ<1>{ static const uint64_t result = 1; }; template<>struct HofQ<2>{ static const uint64_t result = 1; }; // recursive uint64_t rHofQ( uint64_t n ){ if ( n < 3 ) return 1; return rHofQ( n - rHofQ( n - 1 ) ) + rHofQ( n - rHofQ( n - 2 ) ); } // loop // series #include std::vector getHofQSerie( uint64_t n ){ std::vector serie = {0,1,1}; for ( uint64_t i = 3 ; i <= n ; ++i ) serie.push_back( serie[ i - serie[ i - 1 ] ] + serie[ i - serie[ i - 2 ] ] ); return serie ; } // get value uint64_t getHofQ( uint64_t n ){ return getHofQSerie( n )[ n ] ; } #include #include void printCompare( std::vector table ){ std::cout << " * * Hofstadter's Q(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 << "Q(" << std::setw(3) << std::right << i << ") : " << std::setw(10) << std::right << table[ i ] << std::setw(10) << std::right << rHofQ( i ) << "\n"; } } using namespace std; int main() { cout << "Hofstadter's Q(30)\n" << " * compile time<> : " << HofQ<30>::result << "\n * runtime recursion : " << rHofQ(30) << "\n * runtime loop : " << getHofQ(30) << endl << endl; cout << "Loop uses a continer to add elements from previous making it more simple and optimized\nFor example :\nF(100000) : " << getHofQ( 100000 ) << endl << endl; printCompare( getHofQSerie( 20 ) ); return 0; }

Algorithms [Jhon Wells] Hofstadter's Q sequence