Memoization examples created by ortonomy - https://repl.it/I5EQ/3

Memoization examples.js

// All ES6 functions
// Used for showing how memoization saves execution cycles
let counter = 0;

// Naive Fibonacci function that calculates every value of a Fibonacci number from 0 every time it's called.
let fibNaive = (n) => {
    counter++
    console.log("fibNaive call #: " + counter);
    return n < 2 ? n : fibNaive(n-1) + fibNaive (n-2);
};

// fibNaive(8);

// A memoized Fibonacci function that uses closures to keep a record of the calculated Fibonacci numbers and only call the function again when it's missing a value.
let fibMemoed = () => {
    let memo = [0,1];
    let fib = (n) => {
        counter++
        console.log("fibMemo call #: " + counter);
        result = memo[n];
        if ( typeof result !== 'number' ) {
            result = fib(n-1) + fib(n-2);
            memo[n] = result;
        }
        return result;
    };
    return fib;
};

let fibImproved = fibMemoed();
// fibImproved(7);

// A generalised memoization function. This is a bit more difficult to understand, as it takes advantage of passing functions as arguments to other functions.

// Function definition.
// @arg1 'memo' is an initial memo array of values
// @arg2 'fundamental' is a function
// this just defines the function 'memoizer', nothing is initialised yet
let memoizer = (memo, fundamental) => {
    let shell = (n) => {
        counter++
        console.log("fibMemo call #: " + counter);
        let result = memo[n];
        if ( typeof result !== 'number' ) {
            result = fundamental(shell, n);
            memo[n] = result;
        }
        return result;
    }
    return shell;
};

// memoized Fibonacci function
// What happens here?
// @arg2 function is the 'fundamental' in the previous defintion. This function will be called every time there is no result available in the memo array, just like the original memo function. You should put the core logic of the recursive call into 'fundamental'. In this case, a function that calculates the Fibonacci number based on the two previous Fibonacci numbers.

let fibMemoized = memoizer([0,1], (shell, n) => {
    return shell(n-1) + shell(n-2);
});

// So what's this shell? It's another function. It's the function that checks if there's a value available already for that value of n and stores. It's defined in the memoizer function, and actually get's passed as an argument to the fundamental you provided. 
// Wait, what? A function passes a reference to itself before it's even finished being defined?! Yup. Confusing as hell. Let's step through it.

// fibMemoized is now a initialized version of 'shell' from the 'memoizer' function.

console.log(fibMemoized); // [Function: shell]

// However, this fibMemoized  has access to several initialized values through closure: The memo array ([0,1]) and also the function 'fundamental'. This context is fixed and will always remain available to shell. (It's bad practice to modify arguments of a function directly, but in this case it's just an example.)
// This is why fundamental, initialized when 'memoized' is called, should take a function and the current value of n as an argument. It should also call 'shell' in itself with the next required values of n, or the recursion will fail.

// It's summary, it's just breaking out the logic of the recursive calculation of n into another function. So, instead of
// fib(n) -> fib(n-1) + fib(n-2) -> ...
// we get
// fibMemoized(n) -> fundamental(shell, n) -> shell (n-1) + shell (n-2) -> fundamental(n) -> ...

// fibMemoized(8);

// We can use this generalised function for factorials too.

let factMemoized = memoizer([1,1], (shell, n) => {
    return n * shell(n-1);
});

factMemoized(10); // 10 times (initial run)
counter = 0;
factMemoized(10); // 1 time 
counter = 0;
factMemoized(5); // 1 time;
counter = 0;
factMemoized(13); // 4 times;

console.log(Object.prototype);