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

Iteration or Recursion?

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

So as a first rule for choosing one implementation over another, when the complexities involved are equivalent, one needs to bear in mind the stack limitations present in the real world when dealing with recursive functions. As such, an iterative approach is always a better one when complexity involved is of n order.

Next, look at a more complex function, the Fibonacci series, which is defined by:

fib(n) = 0 if n == 0
fib(n) = 1 if n == 1
fib(n) = fib(n-1) + fib(n-2) if n >= 2 

As you can figure it out based on this implementation, the series generated by this formula is 0, 1, 1, 2, 3, 5, 8, 13, 21... and so on. Based on this definition, a recursive implementation of the Fibonacci function can be provided — in the fibonacci package. Start again by defining the "contract" in the FibonacciCalculation abstract class:

public abstract class FibonacciCalculation extends SimpleMeasurementImpl 
{
   public abstract long getFibonacci( long n );
}

Next, provide an implementation for the function itself in the RecursiveFibonacci class:

public long getFibonacci(long n) 
{
   steps = 0;
   timeStart = System.nanoTime();
   try
   {
       return computeFibonacci( n );
   }
   finally
   {
       timeEnd = System.nanoTime();
   }
}
 
private long computeFibonacci( long n )
{
   if( n == 0 )
       return 0;
   if( n == 1 )
       return 1;
   steps++;
   return computeFibonacci( n - 1 ) + computeFibonacci( n - 2 );
}

This becomes the following, if you remove the "measurements" code:

public long getFibonacci(long n) 
{
   if( n == 0 )
       return 0;
   if( n == 1 )
       return 1;
   steps++;
   return getFibonacci( n - 1 ) + getFibonacci( n - 2 );
}

In other words, it follows exactly the definition given above.

Now let's see if an iterative implementation for this function can be provided. Note that the Fibonacci function is defined only recursively, however, that doesn't mean an iterative implementation is not possible! The definition, if you recall, was:

fib(n) = 0 if n == 0
fib(n) = 1 if n == 1
fib(n) = fib(n-1) + fib(n-2) if n >= 2 

To provide an iterative implementation, you will have to iterate from 0 to n-1 bearing in mind at each step i that you have already computed the values for fib(i-1) and fib(i-2). You can use this to compute fib(i). Moving on to the next step, you can reuse the values for fib(i-1) and fib(i). Therefore an iterative implementation will look like the one in class IterativeFibonacci (again, the code required for measurements has been taken out):

public long getFibonacci(long n) 
{
   if( n == 0 )
       return 0;
   if( n == 1 )
       return 1;
   long result = 0;
   long n_1 = 1;
   long n_2 = 0;
   while( n > 1 )
   {
      result = n_1 + n_2;
      n_2 = n_1;
       n_1 = result;
       n--;
   }
   return result;
}

If you compare the complexities of the two implementations provided, a quick glance reveals that the recursive one makes two call to itself at each step. This provides a perfect example of "tree recursion", which has an exponential complexity — while the iterative one is of linear complexity. Running these two in parallel (see the Fibonacci class in the default package) provides the following result, for computing fib(20):

Iterative Fibonacci result for 20
Steps : 19
Nanos : 9468
 
Recursive Fibonacci result for 20
Steps : 10945
Nanos : 1043673

Even without the time measurements, anyone can see straight away that the iterative solution should be the preferred one due to the number of iterations/steps required. This is true even for really low values of the n. While stack overflow can occur here for large values, it is not the purpose of this example to re-iterate the stack overflow problem, but instead to underline the fact that one should try to map a recursive definition to an iterative one as well and compare their complexities before deciding on the implementation, even if the problem given only "suffers" a recursive definition. This is even more obvious for cases like the Fibonacci series, which follow a tree recursive definition and therefore provide exponential complexity.

Just because your "requirement specifications" outlines a recursion, it doesn't mean you should proceed straight away to implementing it recursively. It is always worth analyzing whether an alternative (iterative?) implementation could be a better choice.


Tags: Java, programming, patterns



Page 3 of 4



Comment and Contribute

 


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

 

 


Sitemap | Contact Us

Rocket Fuel