# Iteration or Recursion?

Now, the first implementation is the iterative one, in the IterativeFactorial class, and it's a very simple one:

public long getFactorial( long n ) { timeStart = System.nanoTime(); steps = 0; long result = 1; while( n > 1 ) { result *= n--; steps++; } timeEnd = System.nanoTime(); return result; }

If you take out the bits required by the measurements, the implementation actually looks like this:

public long getFactorial( long n ) { long result = 1; while( n > 1 ) result *= n--; return result; }

This maps to the iterative definition provided above for the factorial, where you loop over all the values from 1 to n and multiply them together. This does mean of course that the complexity of such an approach is O(n).

Now look at the recursive implementation of the same factorial, provided in the RecursiveFactorial class:

public long getFactorial(long n) { timeStart = System.nanoTime(); steps = 0; try { return computeFactorial( n ); } finally { timeEnd = System.nanoTime(); } } private long computeFactorial( long n ) { if( n <= 1 ) return 1; steps++; return n * computeFactorial( n - 1 ); }

The first thing you will notice is that the implementation has been broken down into two functions, a "wrapper" (getFactorial) and the actual recursive function computeFactorial. While that might seem odd at first glance, a closer look reveals that this pattern has been applied so the "measurements" (start/end time and number of steps) can properly be initialized. Removing the measurements from the implementation would render the following implementation:

public long getFactorial(long n) { return computeFactorial( n ); } private long computeFactorial( long n ) { if( n <= 1 ) return 1; return n * computeFactorial( n - 1 ); }

You will notice that the try/finally gets removed since the finally clause will have an empty "body". And looking at the above getFactorial becomes just a function that delegates the call to coputeFactorial, so you can merge the two of them into a single call:

public long getFactorial( long n ) { if( n <= 1 ) return 1; return n * getFactorial( n - 1 ); }

As stated before, this pattern was implemented purely so all of the measurements could be added into the code. You will notice the same pattern of splitting the implementation into two parts applied to all the other recursive implementations discussed in here, for the same reason.

The implementation shown above maps perfectly onto the recursive definition of the factorial function provided above and just as in the case of the iterative one, the complexity involved is still O(n) as ultimately you will end up cycling through all the numbers from 1 to n and multiply them.

So at first sight, the two implementations are completely identical from a computational point of view, thus leaving the choice of one over another to pure personal preference of the programmer. Is this definitely the case though? Since you do have some basic comparisons, run the two implementations side by side and look at the numbers. A "side by side" comparison has been provided in the Factorial class in the default package, in the main function:

public static void main( String args[] ) { FactorialCalculation fact = new IterativeFactorial(); long n = 1000; try { fact.getFactorial( n ); } finally { measure( "Iterative factorial result for " + n, fact ); } fact = new RecursiveFactorial(); try { fact.getFactorial( n ); } finally { measure( "Recursive factorial result for " + n, fact ); } }

As you can see, this is a very simple idea. The factorial of 1000 is going to be computed using the iterative approach and then using the recursive implementation. On my PC this execution renders the following result:

Iterative factorial result for 1000 Steps : 999 Nanos : 115101 Recursive factorial result for 1000 Steps : 999 Nanos : 297800

As I signaled before, the steps member is not a precise measurement, but rather a measure of how many cycles/loops have taken place. As such, in both cases this is 999 — since the case of n=1 is not considered a step. So as expected, both implementations take the same number of steps.

The recursive one seems, however, to take longer!?

So that's a first signal that perhaps personal preference is not the best way to decide over these two implementations. Furthermore, let's push this even further and see how you can cope with the likes of computing the factorial of 10,000.j A number 10 times bigger suggests that you should expect 10 times more steps (obviously!) and 10 times longer to complete. The result probably comes as no surprise:

Iterative factorial result for 10000 Steps : 9999 Nanos : 1510994 Recursive factorial result for 10000 Steps : 5347 Nanos : 3102287 Exception in thread "main" java.lang.StackOverflowError at factorial.RecursiveFactorial.computeFactorial(RecursiveFactorial.java:24) at factorial.RecursiveFactorial.computeFactorial(RecursiveFactorial.java:24) ...

While the iterative function still completes (though indeed, the computation would exceed the size of a long data type so it just returns a 0), on my machine, the recursive one bails out around step 5000 as it runs out of stack space. (It also takes more time to execute as our timing measurements show, but I will get back to that one.)

Page 2 of 4

*This article was originally published on April 23, 2009*