To calculate the nth term of the fibonacci sequence, I have the familiar recursive function:

var fibonacci = function(index){
    if(index<=0){ return 0; }
    if(index===1){ return 1; }
    if(index===2){ return 2; }

    return fibonacci(index-2) + fibonacci(index-1);
}

This works as expected. Now, I am trying to store calculated indices in an object:

var results = {
  0: 0,
  1: 1,
  2: 2
};

var fibonacci = function(index){
    if(index<=0){ return 0; }
    if(index===1){ return 1; }
    if(index===2){ return 2; }

    if(!results[index]){
        results[index] = fibonacci(index-2) + fibonacci(index-1);
    }
}

I know this isn't actually increasing performance since I'm not accessing the results object, but I wanted to check first if my results object was being populated correctly before memoizing. Unfortunately, it isn't. For fibonacci(9), I get:

Object {0: 0, 1: 1, 2: 2, 3: 3, 4: NaN, 5: NaN, 6: NaN, 7: NaN, 8: NaN, 9: NaN}

Why am I getting NaN for indices past 3?

To calculate the nth term of the fibonacci sequence, I have the familiar recursive function:

var fibonacci = function(index){
    if(index<=0){ return 0; }
    if(index===1){ return 1; }
    if(index===2){ return 2; }

    return fibonacci(index-2) + fibonacci(index-1);
}

This works as expected. Now, I am trying to store calculated indices in an object:

var results = {
  0: 0,
  1: 1,
  2: 2
};

var fibonacci = function(index){
    if(index<=0){ return 0; }
    if(index===1){ return 1; }
    if(index===2){ return 2; }

    if(!results[index]){
        results[index] = fibonacci(index-2) + fibonacci(index-1);
    }
}

I know this isn't actually increasing performance since I'm not accessing the results object, but I wanted to check first if my results object was being populated correctly before memoizing. Unfortunately, it isn't. For fibonacci(9), I get:

Object {0: 0, 1: 1, 2: 2, 3: 3, 4: NaN, 5: NaN, 6: NaN, 7: NaN, 8: NaN, 9: NaN}

Why am I getting NaN for indices past 3?

• javascript
• recursion
• fibonacci

• 1 Because your function doesn't return anything when index > 2. – JJJ Commented Nov 22, 2015 at 23:30
• @Juhana Oh man I'm silly. Thank you. Can you submit an answer so I can accept it? – PDN Commented Nov 22, 2015 at 23:33
• 2 Not directly related to your problem, but if you are prepopulating the results array, then why do you also need to explicitly test for index within the function? Also, fib(2) is 1 I believe. – user663031 Commented Nov 23, 2015 at 4:43
• Following up on the previous comment, you'd be best off simply removing 2 from the cache and removing if(index===2){ return 2; } from the code. The Fibonacci sequence is, depending upon who you ask, either 0, 1, 1, 2, 3, 5, 8, ... or 1, 1, 2, 3, 5, 8, .... Notice that in either case there are two 1s. – Scott Sauyet Commented Jun 11, 2020 at 14:52

9 Answers 9

Here's a solution using "Helper Method Recursion":

function fib(n) {
  const memorize = {};

  function helper(n) {
    if (n in memorize) return memorize[n];
    if (n < 3) return 1;
    return memorize[n] = helper(n - 1) + helper(n - 2);
  }

  return helper(n);
}

Here is my solution:

function fib(n, res = [0, 1, 1]) {
    if (res[n]) {
        return res[n];
    }

    res[n] = fib(n - 1, res) + fib(n - 2, res);
    return res[n];
}

console.log(fib(155));

The recursive Fibonacci consume too much processing power which is not good for application. to improve this we use Memoization. which keeps the computed result store in Array. so next when the same value comes it will simply return the Stored value from the computed Array.

function memoizeFibonacci(element, memo = {}) {
  if (element < 3) return 1;
  if (element in memo) return memo[element];

  memo[element] = memoizeFibonacci(element - 1, memo) + memoizeFibonacci(element - 2, memo);

  return memo[element];
}
let a = 15;
console.log('Memoize febonaci', memoizeFibonacci(a));

Going to close the loop on this answer by posting @Juhana's comment:

"Because your function doesn't return anything when index > 2"

const f = (n, memo = [0, 1, 1]) => memo[n] ? memo[n] : (memo[n] = f(n - 1, memo) + f(n - 2, memo)) && memo[n]

console.log(f(70))

Here're my solutions

With Memoization (Dynamic Programming) (Time complexity approximately O(n))

const results = {}

function fib(n) {
    if (n <= 1) return n

    if (n in results) {
        return results[n]
    }
    else {
        results[n] = fib(n - 2) + fib(n - 1)
    }
    return results[n]

}

console.log(fib(100))

Without Memoization (Time complexity approximately O(2^n))

function fib(n) {
    if (n <= 1) return n

    return fib(n - 1) + fib(n - 2)

}

console.log(fib(10))

Here is my object orientated attempt.

var memofib = {
    memo : {},
    fib : function(n) {
        
        if (n === 0) {
            return 0;
        } else if (n === 1) {
            return 1;
        } else {
            
            if(this.memo[n]) return this.memo[n];
            
            return this.memo[n] = this.fib(n - 1) + this.fib(n - 2);
        }
    }
};


console.log(memofib.fib(10));

Here's my solution achieving memoization using a non-recursive approach.

// The Fibonacci numbers.
// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……..

function fibonacci(n) {
  const map = new Map(); // Objects can also be used
  map.set(0,1); // seed value for f(0)
  map.set(1,1); // seed value for f(1)
  for(let i=2; i < n - 1; i++) {
    const result = map.get(i - 1) + map.get(i - 2);
    map.set(i,result);
  }
  return map.get(n - 2);
}

console.log(fibonacci(20)); // 4181

I have added some additions.

var results = {};

var fibonacci = function (index) {
   if (index <= 0) return 0;

   if (index == 1 || index == 2)  return 1;

   return fibonacci(index - 2) + fibonacci(index - 1);
};

for (var i = 1; i <= 10; i++) {
  results[i] = fibonacci(i);
}

console.log(results);