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