November 22, 2014
Hot Topics:

Iteration or Recursion?

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

For the next exercise, assume that you have enough memory and stack space so that you will never cause a stack overflow, regardless of the inputs. Let's take a look at whether for equivalent recursive and iterative implementations (i.e. implementations that have the same complexity), there are any differences in between the recursions and iterations. For the purpose of this exercise, the package "stack" has been created and the abstract class that defines the "contracts", StackConsumingCalculation. The class itself offers 3 different functions; however, I will be looking at one of them at a time.

First let's look at a function that takes four parameters:

public abstract long stackConsumingCalculation( 
                       String a, int b, long c, Object d );

For simplicity, all this function does, is return a 0 if b == 0, otherwise, it returns stackConsumingCalculation(a, b-1, c, d). It's easy to see the function will always return 0, but only after it iterated through all the values b,b-1,b-2,...,0. As such, the iterative implementation of this function (provided in the IterativeStackConsuming class) looks like this:

public long stackConsumingCalculation( 
                       String a, int b, long c, Object d );
{
   while( b > 0 )
   {
       b--;
       if( b == 0 ) break;
   }
   return 0;
}

The recursive one (provided in RecursiveStackConsuming) looks like this:

public long stackConsumingCalculation( String a, int b, long c, Object d ) 
{
   if( b == 0 )
       return 0;
   steps++;
   return stackConsumingCalculation( a, b-1, c, d );
}

Simply comparing these two implementations (i.e. running the main function provided in StackConsumption class in the default package) renders:

Normal Iterative Stack result for 1000
Steps : 1000
Nanos : 81201
 
Normal Recursive Stack result for 1000
Steps : 1000
Nanos : 319499

This goes to show that even with the same number of steps taken (i.e. equivalent complexities), the recursive one takes longer — quite sensibly longer in fact (about four times!). Since there are no complex operations (computations) involved, the single cause left for this is "stack preparation" — the time it takes internally the JVM to put the parameters on the stack at each step, together with pointers in the code to where the execution should continue once the call is finished. Since you're passing four parameters, at each step four values need to be pushed onto the stack so one idea is to encapsulate these four parameters into a single object, to reduce the number of such operations on each step and see if this makes a difference. In order to test this, class Capsule has been introduced, which simply just wraps these four values:

public class Capsule 
{
   public String a;
   public int b;
   public long c;
   public Object d;
}

A method taking an instance of Capsule as a parameter has been provided in the abstract class StackConsumingCalculation:

public abstract long stackConsumingCapsule( Capsule c );

Now running the test again using the Capsule class, gives the following results:

Encapsulated Iterative Stack result for 1000
Steps : 1000
Nanos : 144241
 
Encapsulated Recursive Stack result for 1000
Steps : 1000
Nanos : 192842

Surprise! The execution times have gotten much closer, which goes to prove that the number of parameters involved is a significant factor when dealing with recursion in real life. This conclusion leads to another idea — what if you only use one parameter that is a primitive data type? To test this, stackConsumingPrimitive function has been added to the abstract class StackConsumingCalculation:

public abstract long stackConsumingPrimitive( int n );

The results of running this test are:

Primitive Iterative Stack result for 1000
Steps : 1000
Nanos : 67137
 
Primitive Recursive Stack result for 1000
Steps : 1000
Nanos : 193543

Ouch! What happened there? We had seemed to be on the right track for getting the execution times closer ! The explanation lies, not surprisingly, in what happens if the following code gets executed:

Stack s = new Stack();
int i = 10;
s.push( i );

I'm sure you've figured out by now — autoboxing! The primitive data type i (int) gets converted into an Integer class that gets pushed onto Stack instance s. There is an extra step of creating an instance of class Integer before pushing the data onto the stack. Similarly (though not identically the same), inside JVM, the primitive types will get wrapped into an object in order to get pushed onto the call stack. Despite using a "simple" data type, more time is actually being spent internally to prepare the call then in the case of using an object!

So when dealing with recursion, another coordinate to take into account is the complexity of the data passed in between calls, and whether this can be simplified by using objects or aggregating them into a single object!

As a last comparative study in this article, you'll look at the greatest common divisor problem, which can be defined using the Euclidean definition:

gcd(x,y) = x if y == 0
gcd(x,y) = gcd(y, x % y), if x >= y > 0 
(obviously, for the other case, x < y, one would just have to swap x and y in this definition)

Following the same pattern as before, package "gcd" was defined, and the "contract" for this computation presented in class GCDComputation:

public abstract class GCDComputation extends SimpleMeasurementImpl 
{
   public abstract long getGCD( long a, long b );
}

The recursive implementation (RecursiveGCD) has been implemented as:

public long getGCD(long a, long b) 
{
   if( a >= b )
       return runGetGCD(a,b);
   else
       return runGetGCD(b,a);
}
 
private long runGetGCD( long a, long b )
{
   if( b == 0 )
       return a;
   return runGetGCD( b, a % b );
}

The iterative one (IterativeGCD) has been implemented as:

public long getGCD( long a, long b ) 
{
   long min, max;
   if( a >= b)
   {
       min = b;
       max = a;
   }
   else
   {
       min = a;
       max = b;
   }
   long temp;
   while( min > 0 )
   {
       temp = min;
       min = max % min;
       max = temp;
   }
   return max;
}

For those who can't detect it, the complexity of the two implementations is equivalent though it has to be noticed that the iterative one requires an extra variable (temp) and extra step needed to swap the min and max values when min becomes greater than max.

Running these two implementations in parallel, gets in most cases slightly bigger times for the recursive one, however, I did manage after the fourth execution to get the following:

Iterative GCD result for 200000, 2001
Steps : 4
Nanos : 11082
 
Recursive GCD result for 200000, 2001
Steps : 4
Nanos : 10867

While this is a result of randomness (as one has to take into account memory usage, CPU load etc at OS level), such a result, where the recursive implementation execution time is shorter than the iterative one cannot be achieved with any of the previous functions provided (trust me, I've tried it!). So this result proves that the recursive implementation is not just "very" equivalent to the iterative one, but in fact it might be a better one occasionally! And that is because the recursive GCD implementation provided here is a "tail-recursive" one. In other words, it is an implementation that doesn't build up any deferred operations (which need to be performed after returning from the recursive call).

If you look at the factorial recursive implementation, having just returned from the call to factorial(n-1), the code still has to multiply that result with n:

public long getFactorial( long n )
{
   ...
   return n * getFactorial( n - 1 );
}

The multiplication in this case is the deferred operation; however, in the case of the recursive GCD, there are no deferred computations/operations left after returning from the recursion. Because of that, modern compilers can optimize tail-recursive functions, since they don't need to save a lot of the information regarding the execution point (in the caller function) when returning from the recursion. So, all the time that was spent before putting things on stack and retrieving them back at each step can be eliminated, thus making the recursive implementation very close (and sometimes better than) the iterative implementation.

Conclusion

While the choice between recursion over iteration or vice versa will always suffer a lot of discussions, there are few basic checks one can perform before going down the wrong route, as shown above. And of course, last but not least one should consider whether a recursive implementation is not somehow easier to understand and maintain than an iterative one, which might be an argument strong enough to overrule all of the above!

Source Code

Source code for article: RecursionandIteration.zip

About the Author

Liviu Tudoris a Java consultant living in the UK with a lot of experience with high-availability systems, mostly in the online media sector. Throughout his years of working with Java, he came to realize that when performance matters, it is the "low level", core Java that makes an application deliver rather than a bloated middleware framework. When the injuries acquired playing rugby with his team, The Phantoms ( http://www.phantomsrfc.com) in London, he writes articles on Java technology for Developer.com.


Tags: Java, programming, patterns



Page 4 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