5 kyu

Memoized Fibonacci

9,989 of 23,826edalorzo

Description:

Problem Context

The Fibonacci sequence is traditionally used to explain tree recursion.

function fibonacci(n) {
    if(n==0 || n == 1)
        return n;
    return fibonacci(n-1) + fibonacci(n-2);
}
def fibonacci(n)
  return n if (0..1).include? n
  fibonacci(n - 1) + fibonacci(n - 2)
end
def fibonacci(n):
    if n in [0, 1]:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)
fibonacci 0 = 0
fibonacci 1 = 1
fibonacci n = fibonacci (n-1) + fibonacci (n-2)
fibonacci = \ n . if (is-zero n)
                    0
                  (if (is-zero (pred n))
                    1
                  # else
                    (add (fibonacci (pred n)) (fibonacci (pred (pred n)))
                  ))
def fibonacci(n: Int): Int = n match {
   case 0 | 1 => n
   case _ => fibonacci(n - 1) + fibonacci(n - 2)
}

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?

Memoization
Refactoring

Stats:

CreatedDec 1, 2013
PublishedDec 1, 2013
Warriors Trained57899
Total Skips14282
Total Code Submissions58720
Total Times Completed23826
JavaScript Completions9989
CoffeeScript Completions69
Ruby Completions1128
Haskell Completions770
Python Completions11824
Scala Completions333
λ Calculus Completions10
Lua Completions102
Total Stars1083
% of votes with a positive feedback rating89% of 2117
Total "Very Satisfied" Votes1711
Total "Somewhat Satisfied" Votes335
Total "Not Satisfied" Votes71
Ad
Contributors
  • edalorzo Avatar
  • jhoffner Avatar
  • nrgarg Avatar
  • Unnamed Avatar
  • logicmason Avatar
  • dburgoyne Avatar
  • anter69 Avatar
  • JohanWiltink Avatar
  • NunoOliveira Avatar
  • fredc Avatar
  • cliffstamp Avatar
  • akar-0 Avatar
  • Kacarott Avatar
  • fcr-- Avatar
  • KayleighWasTaken Avatar
Ad