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?
48 Answers
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));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);
}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 memoizeFabonaci(index, cache = []) { // console.log('index :', index, ' cache:', cache) if (cache[index]) { return cache[index] } else { if (index < 3) return 1 else { cache[index] = memoizeFabonaci(index - 1, cache) + memoizeFabonaci(index - 2, cache) } } return cache[index];
}
let a = 15
console.log('Memoize febonaci', memoizeFabonaci(a))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))Going to close the loop on this answer by posting @Juhana's comment:
"Because your function doesn't return anything when index > 2"
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));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);
