Firstly, here’s a basic implementation of Fibonacci using recursion:

using Numbers = std::vector<unsigned long long>; Numbers cache( 5000, 0 ); unsigned long long fibonacciRecursiveImpl( size_t n, Numbers& cache ) { if ( n == 0 ) return 0ULL; if ( n == 1 ) return 1ULL; if ( cache[n] != 0 ) return cache[n]; auto num = fibonacciRecursiveImpl( n-1, cache ) + fibonacciRecursiveImpl( n-2, cache ); cache[n] = num; return num; } unsigned long long fibonacciRecursive( size_t n ) { return fibonacciRecursiveImpl( n, cache ); }

This works fine for small numbers (e.g. up to 20). I was interested to know where it would fail first, data overflow (due to the size of the numbers involved) or stack overflow (due to the recursive approach)? I implemented this on a MacBook using Apple LLVM 7.0 and the C++14 flag, but no other special switches set. It turns out that the overflow problems kick in for n > 93, but there was no sign of stack overflows, even up for n ~ 2000.

Even if there was a stack overflow, you could still use recursion, but change to a tail recursive solution (many C++ compilers will eliminate tail calls, essentially turning this into an iterative solution):

// Implement recursive approach with possibility for "Tail call elimination", // avoids any concerns about stack overflow unsigned long long fibonacciTailRecursiveImpl( size_t n, unsigned long long prevprev, unsigned long long prev ) { if ( n == 0 ) return prevprev; if ( n == 1 ) return prev; return fibonacciTailRecursiveImpl( n-1, prev, prevprev + prev ); } unsigned long long fibonacciTailRecursive( size_t n ) { return fibonacciTailRecursiveImpl( n, 0, 1 ); }

So how to avoid the data overflow for Fibonacci over n = 93? At that point, you need to introduce a large number type with its own internal representation of large integers and suitable operator+ implementation. I used one such, BigNum, for this HackerRank challenge. The implementation stores the large integer as a string, with each character taking values in the range [0,100]. This reduces the number of digit-by-digit additions by a factor of 10 compared to a straight decimal representation.

I replaced unsigned long long with BigNum in the recursive solution above and verified that it returns the correct answers for n ~ 2000, with no stack overflows. Here, I’ll show it in an iterative solution (if you don’t want to keep a cache around, this is highly memory efficient, because you only need to store the previous two values):

BigNum fibonacciBigNumIterativeImpl( size_t n ) { BigNum prevprev(0); BigNum prev(1); if ( n == 0 ) return prevprev; if ( n == 1 ) return prev; BigNum num(0); for ( size_t i = 2; i <= n; ++i ) { num = prevprev + prev; prevprev = prev; prev = num; } return num; } std::string fibonacciBigNumIterative( size_t n ) { auto result = fibonacciBigNumIterativeImpl( n ); return result.toString(); }