Recursion has always been fascinating to me, also confusing and difficult for me to wrap my head around. I have been watching Douglas Crockford’s Act III: Function the Ultimate. He details many, many things about Functions.

The interesting concept that I had never heard of is called memoization. You add an element in your recursive function that maintains a list of results to steps. For example,

var recursion = function(memo, n){
  var result = memo[n];  //see if memo contains an answer already
  if( result === 'undefined' )
    result = memo[n] = n + recursion(memo, n--);
  return result;
}

As you can see, the function first looks for the result to the function call in the memo array. If it is not found there, it performs a recursive call memo[n] = n + recursion(memo, n–);. This example is overly simplistic for illustrating the concept and relies on the user predefining a list of known calculations to preload the memo anytime they wish to call this. This next example shows a better implementation.

function memoizer(memo, formula){
  var recur = function(n){
    var result = memo[n];
    if( typeof result !== 'number' ){
      result = formula(recur, n);
      memo[n] = result;
    }
    return result;
  };
  return recur;
}
var factorial = memoizer([1,1], function(recur,n){
  return n * recur(n-1);
});

factorial(5); //120
factorial(10); //3628800

Recursive algorithms have complicated execution paths, so I will try to break this down into some steps. Lets start with our instantiation since this is what this memoizer function was defined to optimize. You pass in your memo of known values factorial(0) = 1 and factorial(1) = 1, so our memo is 1,1. The second argument is the recursive function you wish to call, for factorial this is simply

//pass in the recursive function as an argument so that it can be called within the context of this new function
var recur = function(recur,n){ return n * recur(n-1) };

Now the tricky part, memoizer is a closure around the recur function. The recur function now has access to the variables passed into the memoizer. The arguments are whatever the factorial method assigns them as. This way, recur can call itself and all instances of recur share the same variables especially the memo of already calculated values and the function to call recurisevly (passed in by factorial). You can see how this works by copying my code into firebug and calling factorial at the end. You will see something that looks like this stored in factorial:

 function(n){
    var result = memo[n];
    if( typeof result !== 'number' ){
      result = formula(recur, n);
      memo[n] = result;
    }
    return result;
  }

What you are not seeing are some private variables, memo and recur. These have been stored in the memoize closure, jealous yet c++ programmers? Now obviously, without a predefined list of calculated values the factorial function will run forever. We provide it with factorial(0) = 1 and factorial(1) = 1 [1,1], so that when these values are hit we return a number and stop the pattern of recursively executing.

The magic of memoization is that anytime during execution of these recursive functions we store the results of substeps. Factorial(2) = 2 * factorial(1) = 2 * 1 = 2, it stores memo[2] = 2. Now when we execute factorial(3) or factorial(4), the value for factorial(2) is already known and does not need to be calculated it is determined from memo[2].

That’s it for now enjoy memoization, I hope to find a use for this possibly in the Composite Pattern.