javascript fibonacci memoization

Question

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?

Because your function doesn't return anything when index > 2. — JJJ
– 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
– PDN, Commented Nov 22, 2015 at 23:33
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
– 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
– Scott Sauyet, Commented Jun 11, 2020 at 14:52

Christopher Reece · Accepted Answer · 2021-09-03 11:56:19Z

6

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

answered Sep 3, 2021 at 11:56

Christopher Reece

4165 silver badges12 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Aditya Hajare · Accepted Answer · 2020-10-26 04:46:29Z

5

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

answered Oct 26, 2020 at 4:46

Aditya Hajare

1,3911 gold badge16 silver badges25 bronze badges

Comments

Abdul Rehman Kaim Khani · Accepted Answer · 2023-02-27 13:06:09Z

3

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

edited Feb 27, 2023 at 13:06

answered Jun 11, 2020 at 10:16

Abdul Rehman Kaim Khani

1,18010 silver badges16 bronze badges

1 Comment

Scott Sauyet Over a year ago

It's strange that you spell "Fibonacci" correctly in the text but not the code...

PDN · Accepted Answer · 2016-02-13 23:12:10Z

1

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

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

answered Feb 13, 2016 at 23:12

PDN

7914 gold badges13 silver badges29 bronze badges

Comments

artak · Accepted Answer · 2022-03-09 09:08:41Z

1

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

answered Mar 9, 2022 at 9:08

artak

211 bronze badge

1 Comment

Community Over a year ago

As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center.

Sandeep Amarnath · Accepted Answer · 2021-05-30 21:30:01Z

0

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

answered May 30, 2021 at 21:30

Sandeep Amarnath

7,1323 gold badges38 silver badges52 bronze badges

Comments

Donal · Accepted Answer · 2022-02-10 17:29:21Z

0

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

edited Feb 10, 2022 at 17:29

answered Jan 12, 2022 at 22:38

Donal

33.2k10 gold badges69 silver badges75 bronze badges

Comments

Suraj Acharya · Accepted Answer · 2022-08-06 11:28:49Z

0

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

answered Aug 6, 2022 at 11:28

Suraj Acharya

1

Comments

Isabek Tashiev · Accepted Answer · 2015-11-22 23:39:10Z

-1

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

answered Nov 22, 2015 at 23:39

Isabek Tashiev

1,0361 gold badge9 silver badges15 bronze badges

1 Comment

user663031 Over a year ago

This answer does not address the OP's desire to memoize intermediate results.

Collectives™ on Stack Overflow

javascript fibonacci memoization

9 Answers 9

Comments

Comments

1 Comment

Comments

1 Comment

Comments

Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

9 Answers 9

Comments

Comments

1 Comment

Comments

1 Comment

Comments

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related