Matt Garnes
Algorithms and Data Structures
4/20/11
Extra Credit Assignment: Factorial

I decided to use memoization to incrementally compute the factorial of an input x. When you compute for example the factorial of 4, you have to computer 4*3*2*1. Or, 4 * factorial(3). In the original function, factorial, it will take O(n) time. In the memoized version, it will take O(1) time (constant), if the result of factorial(x) is already stored in the results array. If some of the sub problems are stored then the function will take less time than it would before, as some will take constant time. This assumes that the array results is stored as a field in the class and updated each time factorialMem is called. 

Thus, if you call factorialMem(15,1,results), it will take 15 calculations to run. (15*14*13*12*11*...*1)

Then, if you call factorialMem(16,1,results), it will take only two calculations. (16*factorial(15) - from lookup)

This is a large improvement in run time from the from the original recursive function to the memoized version.


	public static double factorial(int x, double result){
		if(x == 1){
			return result;
		}
		return factorial(x-1,result*x);
	}
	
	public static double factorialMem(int x, double acc, double[] results){
		if(x == 1){
			return acc;
		}
		try{
		if(results[x-1] == 0){
			results[x-1] = acc*x;
			return factorialMem(x-1,acc*x, results);
		}
		}
		catch (Exception e){
			results[x] = acc*x;
			return factorial(x-1,acc*x);
		}
		return acc*results[x-1];
	}