Computing for Fibonacci becomes slower after adding Memoization Javascript

February 1, 2022

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

Output: `11`

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

Output: `19`

>Solution :

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