CODEWITHSUNDEEP
javascriptrecursionfibonacci
PDN
PDN

Reputation: 791

javascript fibonacci memoization

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?

Upvotes: 4

Views: 10985

Answers (9)

Abdul Rehman Kaim Khani
Abdul Rehman Kaim Khani

Reputation: 1170

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));

Upvotes: 3

Suraj Acharya
Suraj Acharya

Reputation: 1

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

Upvotes: 0

artak
artak

Reputation: 21

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))

Upvotes: 1

Donal
Donal

Reputation: 32713

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));

Upvotes: 0

Christopher Reece
Christopher Reece

Reputation: 396

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);
}

Upvotes: 6

Sandeep Amarnath
Sandeep Amarnath

Reputation: 6916

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))

Upvotes: 0

Aditya Hajare
Aditya Hajare

Reputation: 1391

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));

Upvotes: 5

PDN
PDN

Reputation: 791

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

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

Upvotes: 1

Isabek Tashiev
Isabek Tashiev

Reputation: 1044

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);

Upvotes: -1

Related Questions