December 20, 2014
Hot Topics:

Iteration or Recursion?

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

Whether we like it or not, recursion is something we encounter very frequently when dealing with applications — even the simplest call to Arrays.sort shows that under the hood there is a recursive quicksort implementation. Whether you like it or not, it is something you need to be aware of and most importantly, the implications of it.

There have been many books written around recursive functions and I'm not going to get involved in a whole discussion about whether recursion could or should be totally avoided or whether that is possible at all (Ackermann function springs to everyone's mind I'm sure). Rather, I'll instead work on the assumption that in the real world most solutions are a mixture of recursive and iterative implementations and because of that there are a few considerations you should factor into your decision. Therefore I'm going to take a comparative look at implementing a few basic functionalities in both a recursive and iterative manners and see what conclusions can be drawn.

In order to perform such a comparison, I'm going to need some basic metrics to allow for comparison in between the 2 implementations in each case. This in itself can suffer a whole discussion as there is more than one coordinate for such measurements, however, for simplicity of such comparisons I'm going to settle for just two parameters: the time it took to complete the operation and the steps taken. Arguably the two are related as it seems logical that the more steps an algorithm takes the more time it will take to finish the execution. This is the real world, however, and there are other things involved in the process of executing a function, as it will transpire soon. Also, it is worth mentioning the "Schroedinger's cat" factor, as introducing these simple measurements will obviously affect the measurements themselves. However, these measurements are not intended to be precise, but are only used for comparison. Any measurement errors introduced shouldn't affect the comparison as long as they are introduced in both implementations and with the same magnitude.

To help with such measurements, I've provided a very simple interface ingeniously named SimpleMeasurement that provides just to methods, one for retrieving the time and one for retrieving the number of steps:

public interface SimpleMeasurement 
{
   public long getNanos();
   public long getSteps(); 
}

While retrieving the number of steps is obvious (getSteps function), the time function seems to have a an obfuscated signature (getNanos). There is a reason behind this madness. On most modern computers, most implementations run in less than a milisecond, so trying to measure the time in miliseconds (let alone seconds) would render zero in most cases for both recursive and iterative implementations. This might lead to the wrong conclusion that both implementations are equally fast. Therefore I decided to go for a finer-grained measurement and measure the time in nanoseconds, which is one billionth of a second. To put it in perspective, 1,000,000 nanoseconds = 1 milisecond.

Each implementation provided for the purpose of this article will have to implement this interface, in order to be able to extract the information that will be used for comparison. Each implementation will have to apply the following pattern when called:

  • Store the current system time in nanoseconds (see javadoc on System.nanoTime. It is safe to use this since it is only being used to compute a difference of starting time and ending time.
  • Reset the counter that counts the number of steps it took to execute the function.
  • Increase the counter for each execution cycle.
  • Store the end system time in nanoseconds at the end of the cycle.

Based on the above steps, each implementation will return (ending time - starting time) for getNanos and the counter value for getSteps.

Since a common pattern has been identified for all of these implementations, it makes sense to provide the basics of this pattern in a class on its own. The SimpleMeasurementImpl class does exactly this. It provides members for start time and end time and the steps counter and also provides implementations for returning the two values:

public class SimpleMeasurementImpl implements SimpleMeasurement 
{
   protected long steps         = 0;
   protected long timeStart   = 0;
   protected long timeEnd    = 0;
   
   public long getNanos() 
   {
       return (timeEnd - timeStart);
   }
 
   public long getSteps() 
   {
       return steps;
   }
}

You will notice that all of the data members have been declared as protected so classes extending this can simply access this data directly. (Remember, this is just for the purpose of some basic measurement metrics, so there is no point in overloading the implementation with encapsulating this data and providing getters and setters which will ultimately add even more execution time to our calls!) In the light of the above each one of our implementation will have to extend this class, and on each call:

  • Initialize timeStart at the beginning of each call (timeStart = System.nanoTime()).
  • Reset the counter (steps = 0).
  • Perform the execution, making sure the counter is incremented at each step (steps++).
  • Initialize timeEnd (timeEnd = System.nanoTime()) at the end.

And the rest is already done for us!

NOTE: You might have noticed a very loose description when it comes to counting the number of steps in the implementations. That's because for the purpose of the comparisons mentioned above, I am not going to actually count every single step taken in the execution of a function, but rather count the number of cycles — the number of times a loop executes or a recursive function calls itself. Since there is already a measurement of time spent executing a function, it isn't necessary to count precisely every single step of the execution (which would have included things like variable assignments, if/then/else tests etc). So simply put, this implementations will have to increment the steps member by one per each step of the loop or each time the recursive function calls itself.

With the basics now implemented, it is time to finally move to the core of this article. The first comparison you're going to look at is the factorial function, for those of you that need their memory refreshed, here's a brief on this function:

n! = 1 if n == 0
n! = 1 * 2 * ... * n if n >= 1

The above definition can be also written in a recursive manner as:

n! = 1 if n == 0
n! = n * (n-1)!

As you can see from the above, the two definitions are identical from a complexity perspective as they both execute in O(n), which ultimately means an algorithm computing these values will have to traverse all of the values from 1 to n to compute this number. For the untrained eye, this means that it doesn't matter which implementation one would go for! Now, see if that is right!

For the purpose of clarity and in order to separate one comparison from another, I've decided to structure each such set of implementations in its own package. The factorial implementation has a corresponding factorial package. For the same clarity reason and in order to clearly separate the iterative and recursive implementation, each package will provide an abstract class that defines the functionality it offers (for instance, computing the factorial) and also provides the basic measurements defined in SimpleMeasurement (by extending the SimpleMeasurementImpl class) and two other classes—one which implements this functionality recursively and another one which implements it iteratively. Also, for each of these you will find a "driver" class in the default package which simply calls the recursive and iterative implementations and then displays the measurements returned by the SimpleMeasurement interface that each such implementation will have to offer. So in the case of the factorial function, you will find inside the factorial package first and foremost an abstract class that defines the "service" this package offers:

public abstract class FactorialCalculation extends SimpleMeasurementImpl
{
   public abstract long getFactorial( long n );
}

No surprise here, the functionality offered in this package is simply to compute the factorial of a number.


Tags: Java, programming, patterns



Page 1 of 4



Comment and Contribute

 


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

 

 


Enterprise Development Update

Don't miss an article. Subscribe to our newsletter below.

Sitemap | Contact Us

Rocket Fuel