musingstudio

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