Recursive algorithms

From Ferrous Moon Research

This article was written by Tycho.

This document is classified ICARS::0, and is for public inspection.

A common method of simplification is to divide a problem into subproblems of the same type. As a computer programming technique, this is called divide and conquer and is key to the design of many important algorithms, as well as being a fundamental part of dynamic programming.

Recursion is exemplified in programming when a function is defined in terms of itself. One example application of recursion is in parsers for programming languages. Recursive algorithms can also be used to walk B-trees, calculate factorials, and solve other such problems. The great advantage of recursion is that an infinite set of possible sentences, designs or other data can be defined, parsed or produced by a finite computer program.

Recurrence relations are equations to define one or more sequences recursively. Some specific kinds of recurrence relation can be "solved" to obtain a non-recursive definition.

Example

In the case of a factorial problem, you could use a recursive function like this:

int factorial ( int _n )
{
   if ( _n == 0 )
      return ( 1 );
   else
      return ( _n * factorial ( _n - 1 ) );
}

A non-recursive version of this function could take this form:

int factorial ( int n )
{
   for ( int j = n - 1; j > 0; j-- )
   {
      n *= j;
   }
   return n;
}

The recursive form seems much more pleasing to the eye, but is actually very sloppy programming. When a function is called, that function is pushed onto the stack. When it's called recursively, you may get it pushed onto the stack way too many times. This eventually consumes enough resources that there is a noticeable slowdown.

Benchmark

In our benchmark, we compared the above two factorial functions using the Intel C++ Compiler v9.1. Each test run consisted of calculating the factorial of numbers between 1 and 4096, inclusive. The test was run 500 times on each function to magnify the timing differences in the long-run. So, using CrissCross API for the Stopwatch class, the benchmark was timed thusly:

Stopwatch *sw = new Stopwatch();
sw->Start();
for ( i = 0; i < 500; i++ )
  for ( j = 1; j <= loop_count; j++ )
    result = factorial ( j );
sw->Stop();
console->WriteLine ( "%lf seconds elapsed, last result = %d", sw->Elapsed(), result );

The test was run at real-time priority (THREAD_PRIORITY_TIME_CRITICAL), on one processor core at once, as to not affect the timings with a second core hindering or enhancing the performance.

It took 27.205 seconds to run the recursive function, and only 10.138 seconds to run the non-recursive one. The recursive calling really hindered speed, causing the recursive function to take 2.7 times longer. This kind of a performance hit is unacceptable.

Conclusions

It's disappointing to know that recursive algorithms are taught in computer science courses without anyone considering the performance ramifications in such coding. Recursive algorithms are an interesting idea, but due to the nature of how computers process information, they are not feasible for complex or time-consuming tasks, as they will only lengthen the process. Recursive functions should always be avoided where possible.