July 31, 2014
Hot Topics:
RSS RSS feed Download our iPhone app

Iteration or Recursion?

  • April 23, 2009
  • By Liviu Tudor
  • Send Email »
  • More Articles »

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.)


Tags: Java, programming, patterns



Page 2 of 4



Comment and Contribute

 


(Maximum characters: 1200). You have characters left.

 

 


Sitemap | Contact Us

Rocket Fuel