Comparing the two versions, it seems that the one using memoization is slower when it should be faster in theory. Why is this the case?
Without Memoization:
function fibonacci(n) {
if (n <= 1) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
const start = Date.now();
fibonacci(22);
const duration = Date.now() - start;
console.log(duration);11With Memoization:
function fibonacci(n, dic = {}) {
if (n <= 1) {
return 1;
}
if (dic[n]) {
return dic[n];
}
let res = fibonacci(n - 1) + fibonacci(n - 2);
dic[n] = res
return res
}
const start = Date.now();
fibonacci(22);
console.log(Date.now() - start);19In your memoized version, you're forgetting to pass dic down the recursive call stack. So it gets the default every time.
When you pass it, the time drops to zero on my machine (That way of measuring performance is not particularly accurate - clearly its not zero!)
function fibonacci(n, dic = {}) {
if (n <= 1) {
return 1;
}
if (dic[n]) {
return dic[n];
}
let res = fibonacci(n - 1,dic) + fibonacci(n - 2,dic);
dic[n] = res
return res
}
const start = Date.now();
fibonacci(22);
console.log(Date.now() - start);