16 - Memoized Fibonacci

Don't say so much, just coding...

Instruction

Problem Context

The Fibonacci sequence is traditionally used to explain tree recursion.

This algorithm serves welll its educative purpose but it's tremendously inefficient, not only because of recursion, but because we invoke the fibonacci function twice, and the right branch of recursion (i.e. fibonacci(n-2)) recalculates all the Fibonacci numbers already calculated by the left branch (i.e. fibonacci(n-1)).

This algorithm is so inefficient that the time to calculate any Fibonacci number over 50 is simply too much. You may go for a cup of coffee or go take a nap while you wait for the answer. But if you try it here in Code Wars you will most likely get a code timeout before any answers.

For this particular Kata we want to implement the memoization solution. This will be cool because it will let us keep using the tree recursion algorithm while still keeping it sufficiently optimized to get an answer very rapidly.

The trick of the memoized version is that we will keep a cache data structure (most likely an associative array) where we will store the Fibonacci numbers as we calculate them. When a Fibonacci number is calculated, we first look it up in the cache, if it's not there, we calculate it and put it in the cache, otherwise we returned the cached number.

Refactor the function into a recursive Fibonacci function that using a memoized data structure avoids the deficiencies of tree recursion Can you make it so the memoization cache is private to this function?

Ruby

Init

  def fibonacci(n)
    return n if (0..1).include? n
    fibonacci(n - 1) + fibonacci(n - 2)
  end

Sample Testing

  Test.assert_equals(fibonacci(50), 12586269025)
  Test.assert_equals(fibonacci(60), 1548008755920)
  Test.assert_equals(fibonacci(70), 190392490709135)

Javascript

Init

  var fibonacci = function(n) {
    if(n == 0 || n == 1)
        return n;
    return fibonacci(n-1) + fibonacci(n-2);
  }

Sample Testing

  describe("Kata Test Suite", function(){
    it("should calculate large Fibonacci numbers", function(){
      Test.assertEquals(fibonacci(70), 190392490709135);
      Test.assertEquals(fibonacci(60), 1548008755920);
      Test.assertEquals(fibonacci(50), 12586269025);
    });
  });

Thinking

想法(1): 斐波那契数列 為最經典的面試考題，從 Init 初始化的題目可以看出來不考慮到記憶體的情況下的解法及想法。
想法(2): 小於 1~2 的時候應該回傳傳進來的值，更大的數可以透過 遞迴 來執行

圖片來源：Unsplash Radek Grzybowski

Hint & Reference

• Ruby
  • Ruby - apidock Keys
  • Ruby - apidock Include?
• JavaScript
  • JS - MDN Typeof

Solution

Ruby

  # Solution 1
  Fibs = {}
  
  def fibonacci(n)
    return n if n == 0 || n == 1
    return Fibs[n] if Fibs.keys.include?(n)
    Fibs[n] = fibonacci(n - 1) + fibonacci(n - 2)
  end

Javascript

  // Solution 1
  var fibonacci = (function() {
    var memo = [0, 1];
    var fib = function(n){
        var result = memo[n];
        if(typeof result !== 'number'){
          result = fib(n - 1) + fib(n - 2);
          memo[n] = result;
        }
        return result;
    }
    return fib;
  })();
  
  // Solution 2
  var fibonacci = (function () {
      var cache = {};

      return function(n) {

        if(n == 0 || n == 1)
            return n;
        if(cache[n - 2] === undefined)
          cache[n - 2] = fibonacci(n - 2);
        if(cache[n - 1] === undefined)
          cache[n - 1] = fibonacci(n - 1);

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