Memoized Fibonacci

Memoized Fibonacci

Memoized Fibonacci

Example:
MemoizedFibonacci(12); 144
MemoizedFibonacci(8); 21
MemoizedFibonacci(15); 610 

function MemoizedFibonacci(index, cache) {
  cache = cache || [];

  if (cache[index]) return cache[index];
  else {
    if (index < 3) return 1;
    else {
      cache[index] = MemoizedFibonacci(index-1,cache)+ MemoizedFibonacci(index-2,cache);
    }
  }
  return cache[index]
}

MemoizedFibonacci(12); 144
MemoizedFibonacci(8); 21
MemoizedFibonacci(15); 610
We create a function MemoizedFibonacci with parameters of index and cache we use cache = cache   [] which is essentialy as the second parameter when invoking is empty array

The base is when we check if cache has the index and if it does it returns the cache of index

In the else clause we check recursively and used cache[index] = MemoizedFibonacci(index-1,cache)+ MemoizedFibonacci(index-2,cache); This is familiar from basic recursively Fibonacci

In the end we return cache[index] since we store the recursively function in cache[index];

comments powered by Disqus