How to calculate Fibonacci sequence for large numbers

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();
}

```