## Recursion in JavaScript

Mar 29, 2010Recursion 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.