Cached Fibonacci calculator implementation

In this post we will see a simple usage of a cache system to accelerate Fibonacci sequence calculator.

Problem

Fibonacci sequence could be implemented by using a recusrive function like following :

int fibo(int n){

  if(n == 0) {
    return 0;
  }
  if(n == 1) {
    return 1;
  }

  return fibo(n-2) + fibo(n-1);
}

… But the above approach is not efficient for big numbers. For example on dartpad.dartlang.org i wasn’t abble to caltulate fibo() for n = 100, because the worklaod was too high for web browser.

Solution

We can make something much better by adding a cache. In bellow gist sample, we use a Dictionnary Map<int, int> as in memory cache.

//In-memory cache in real project tah can be à key/val storelike redis.
Map<int, int> cache = new Map();

int fibo(int n){

  if(cache.containsKey(n))
  {
    return cache[n];
  }
  
  int result;
  if(n == 0) {
    result = cache[0] = 0;
    return result;
  }
  if(n == 1) {
    result = cache[1] = 1;
    return result;
  }

  result =  fibo(n-2) + fibo(n-1);
  cache[n] = result;
  return result;
}

With this version i can run my calculator for n = 100 or n = 1000 without any problem on my web browser.

Try it here

Attention points

• Cache size : A too big cache can cause performance problems.
• The cache storage layer must be very fast to read/write value to have best perrformances.
• Redis is a very popular open source in-memory data structure store.