Fibonacci Sequence (Memoization)¶

You may want to see the pages Fibonacci Sequence and Dictionaries first.

The last page on the Fibonacci Sequence showed a simple example of finding Fibonacci numbers, but the example was really inefficient. Here, we are going to make a much faster version with a concept called “memoization”. Not “memorization”, “memoization”. To see why the last one was so slow, here’s a diagram of when we try to find the sixth fibonacci number:

As you can see, this sort of tree would get much larger as we try to find later fibonacci numbers. You can also see we are finding the same values multiple times - fib(2), for instance, is calculated five times. When there is a recursive problem like this with repeated calculations, the entire idea of “memoization” is to store values that are found and use them if they are ever asked for again. That way, we only do each calculation once. Here is that same diagram, but with repetitions removed:

Images from this page.

You’ll notice that we only do six calculations this time (the blue box represents reading a previous calculation). So, we’ve reduced a problem with O(2^n) calculations down to O(n) calculations, or linear time (here is a page on that: Time and Space Complexities).

While the previous implementation was limited to the 30th or so Fibonacci number because of time, this implementation is only limited by the size of the available integer types. It gets the 64th Fibonacci number in second(s), for example, where the other implementation might have taken hours.

The found values are stored in a Dictionaries.

#include <iostream>
#include <unordered_map>
using namespace std;

long fib(long n, unordered_map<long, long> &memo){
  if(n == 0 || n == 1)
    return n;
  if((memo.find(n) == memo.end()))
    memo[n] = fib(n-1, memo) + fib(n-2, memo);
  return memo[n];
}

long fibMemo(long n){
  unordered_map<long, long> memo;
  return fib(n, memo);
}

int main(){
  cout << fibMemo(64) << endl;
  return 0;
}

using System.Collections.Generic;
class Program{
  static long fib(long n, ref Dictionary<long, long> memo){
    if(n == 0 || n == 1)
      return n;
    if(!memo.ContainsKey(n))
      memo[n] = fib(n-1, ref memo) + fib(n-2, ref memo);
    return memo[n];
  }
  static long fibMem(long n){
    Dictionary<long, long> memo = new Dictionary<long, long>();
    return fib(n, ref memo);
  }
  static void Main(string[] args){
    System.Console.WriteLine(fibMem(64));
  }
}

import java.util.*;
public class fibonacciMem{
  public static long fib(long n, Map<Long, Long> memo){
    if(n == 0 || n == 1)
      return n;
    if(!memo.containsKey(n))
      memo.put(n, fib(n-1, memo) + fib(n-2, memo));
    return memo.get(n);
  }
  public static long fibMem(long n){
    Map<Long, Long> memo = new HashMap<Long, Long>();
    return fib(n, memo);
  }
  public static void main(String[] args) {
    System.out.println(fibMem(64));
  }
}

function fibMem(n){
  var memo = {};
  function fib(m){
    if(m === 0 || m === 1)
      return m;
    if(!(m in memo))
      memo[m] = fib(m-1) + fib(m-2);
    return memo[m];
  }
  return fib(n);
}
console.log(fibMem(64));

def fibMem(n):
  memo = {}
  def fib(m):
    if m == 0 or m == 1:
      return m
    if not (m in memo):
      memo[m] = fib(m-1) + fib(m-2)
    return memo[m]
  return fib(n)

print(fibMem(64))

func fibMem(_ n: Int) -> Int {
  var memo = [Int : Int]()
  func fib(_ m: Int) -> Int {
    if m == 0 || m == 1 {
      return m
    }
    if memo[m] == nil {
      memo[m] = fib(m-1) + fib(m-2)
    }
    return memo[m]!
  }
  return fib(n)
}
print(fibMem(64))