The Javascript’s Memorization Function to Speed Up Recursion (Dynamic Programming)

We all know the Fibonacci function is defined as F(N) = F(N – 1) + F(N – 2) and the terminating conditions are F(1) = 1 and F(0) = 0. We can implement such using recursion but that won’t be the most efficient.

1
2
3
4
5
6
7

var f = function(n) {
    switch (n) {
        case 0: return 0;
        case 1: return 1;
        default: return f(n - 1) + f(n - 2);
    }
}

var f = function(n) {
    switch (n) {
        case 0: return 0;
        case 1: return 1;
        default: return f(n - 1) + f(n - 2);
    }
}

As for intermediate values e.g. f(n – 2) it will be calculated more than once. f(n – 1) relies on f(n – 2) and f(n – 3) while f(n – 2) reliese on f(n – 3) + f(n – 4) where you can see f(n – 3) is calculated twice. If n is large, it will not be possible to obtain the Fibonacci value as the recursive function does repetitive calculations.

We can write a Javascript function that takes a function as parameter and this function will remember the intermediate values as the function calculates recursively.

1
2
3
4
5
6
7
8
9
10
11
12

var memorizationFunc = function(func) {
    let cached = {}; // hash table to store the intermediate values
    return function() {
        let key = [].slice.call(arguments, 0); // convert arguments to array.
        if (cached[key]) { // has this been calculated before?
            return cached[key]; // return the value so we don't need to compute it
        }
        let val = func.apply(this, arguments); // call the function with arguments
        cached[key] = val; // save the value to the cached table
        return val;
    }
}

var memorizationFunc = function(func) {
    let cached = {}; // hash table to store the intermediate values
    return function() {
        let key = [].slice.call(arguments, 0); // convert arguments to array.
        if (cached[key]) { // has this been calculated before?
            return cached[key]; // return the value so we don't need to compute it
        }
        let val = func.apply(this, arguments); // call the function with arguments
        cached[key] = val; // save the value to the cached table
        return val;
    }
}

Then, we just have to pass the function like this:

1
2
3
4
5
6
7

var f = memorizationFunc(function (n) {
    switch (n) {
        case 0: return 0;
        case 1: return 1;
        default: return f(n - 1) + f(n - 2);
    }
});

var f = memorizationFunc(function (n) {
    switch (n) {
        case 0: return 0;
        case 1: return 1;
        default: return f(n - 1) + f(n - 2);
    }
});

The console.log(f(100)) will return 354224848179262000000 quickly.

NodeJs / Javascript

The Dynamic Programming (DP) algorithms can be mostly implemented using recursions (sub problems) with memorization as the intermediate values need to be stored.

–EOF (The Ultimate Computing & Technology Blog) —