loops versus recursion

I was reading this article about the subject at Ars Technica, and a lot of people talking about how using recursion over loops is the Right Thing(tm) to do. And, of course, a lot of other people questioning this.

So, I decided to write a simple, näive code snippet to verify and take my own conclusions. Here it follows:

  Code:

/**
 * rectest.c
 **/
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

clock_t start, end;
float   *values = NULL;
int      valuesLength = 0;


float   averageWithLoop (float * myArray, int size)
{
   float   average, sumValues = 0.0f;
   int      i;

   for (i = 0; i < size; i++)
   {
      sumValues += myArray[i];
   }

   average = ((float)sumValues/size);
   return average;
}

float   averageWithRecursion (float *myArray, int size)
{
   if (size == 2)
   {
      return   ((float)(myArray[0] + myArray[1])/2);
   }

   return ((averageWithRecursion (myArray, (int)(size / 2)) + averageWithRecursion (&myArray[(int)(size / 2)], (int)(size / 2)))/2);
}

void   doAverage (int recursive)
{
   if (recursive)
   {
      printf ("Average (recursive) = %f\n", averageWithRecursion (values, valuesLength));
   }
   else
   {
      printf ("Average (loop) = %f\n", averageWithLoop (values, valuesLength));
   }
}

int      main (int argc, char **argv)
{
   int      i;

   valuesLength = 16 * 1024 * 1024;
   values = (float *)malloc (sizeof (float) * valuesLength);
   if (!values)
   {
      printf ("Unable to alloc %i float values\n", valuesLength);
      exit (-1);
   }

   for (i = 0; i < valuesLength; i++)
   {
      values[i] = ((float)rand()/RAND_MAX);
   }

   start = clock();
   doAverage ((argc > 1) ? 1 : 0);
   end = clock ();
   printf ("Elapsed clock ticks: %i\n", end - start);
   return      0;
}


Now I know I am just a mediocre C programmer, and probably there are better ways to do what I did, but I was just trying to prove a point: that even a mediocre programmer could see some benefits by simply using recursion. Alas, the above recursive code compiled using MSVC 2008 with /Ot performed quite poorly compared to the loop based version (more like 10x slower in a 2nd generation i5 CPU; I didn't bother trying to test in my Phenom II, but probably the results would look even worse) and to my dismay the different solutions shows slightly different results, indicating either I am doing something wrong in the recursive function or worse, that there's precision lost.

So, I'd like to hear from you guys what do you think about the subject, and how could I improve/fix the recursive code above so it can perform at least as good as the loop version ?

EDIT:Regarding the precision loss, I managed to fix it simply working with double precision variables and returns in both functions. Still, the performance loss remains unchanged.

try a compiler that has decent tail recursion optimisations, so that it compiles it into a loop instead of actually recursing.
either way, your algorithm is different. your recursion version has an aweful lot more divides, and they're floats so they won't be optimised into simple bitshifts (read: expensive).

try a compiler that has decent tail recursion optimisations, so that it compiles it into a loop instead of actually recursing.
either way, your algorithm is different. your recursion version has an aweful lot more divides, and they're floats so they won't be optimised into simple bitshifts (read: expensive).

About the lot of divisions, I am writing it in a way most average programmers would do. I was more concerned in writing correct code first; performance comes later.
Either way, what you're saying basically is: to see any real benefit it takes a lot of effort, like changing to compilers that do support TCO (and this may not be an option in many cases), writing carefully crafted code that not explodes the stack, so in the end the compiler can convert it into... a loop.

Well, thanks for confirming what I already suspected.

Following Spike's suggestion, I removed float divisions from both functions. Code now looks like this:

  Code:

/**
 * rectest.c
 **/
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

clock_t start, end;
float   *values = NULL;
int      valuesLength = 0;


double   sumWithLoop (float *myArray, int size)
{
   double   sumValues = 0.0f;
   int      i;

   for (i = 0; i < size; i++)
   {
      sumValues += (double)myArray[i];
   }

   return sumValues;
}

double   sumWithRecursion (float *myArray, int size)
{
   int   newSize;
   if (size == 2)
   {
      return   ((double)(myArray[0] + myArray[1]));
   }

   newSize = size >> 1;
   return ((sumWithRecursion (myArray, newSize) + sumWithRecursion (&myArray[newSize], newSize)));
}

void   doAverage (int recursive)
{
   if (recursive)
   {
      printf ("Average (recursive) = %f\n", (double)sumWithRecursion (values, valuesLength)/valuesLength);
   }
   else
   {
      printf ("Average (loop) = %f\n", (double)sumWithLoop (values, valuesLength)/valuesLength);
   }
}

int      main (int argc, char **argv)
{
   int      i;

   valuesLength = 256 * 1024 * 1024;
   values = (float *)malloc (sizeof (float) * valuesLength);
   if (!values)
   {
      printf ("Unable to alloc %i float values\n", valuesLength);
      exit (-1);
   }

   for (i = 0; i < valuesLength; i++)
   {
      values[i] = ((float)rand()/RAND_MAX);
   }

   start = clock();
   doAverage ((argc > 1) ? 1 : 0);
   end = clock ();
   printf ("Elapsed clock ticks: %i (clocks per second: %i)\n", end - start, CLOCKS_PER_SEC);
   return      0;
}


Also, I increased the array size to 256 million of floats, added the CLOCKS_PER_SEC current value and tested using the release build. Results follows:

  Code:

C:\projetos\games\recursiontests\Release>recursiontests.exe
Average (loop) = 0.500024
Elapsed clock ticks: 273 (clocks per second: 1000)

C:\projetos\games\recursiontests\Release>recursiontests.exe foo
Average (recursive) = 0.500024
Elapsed clock ticks: 777 (clocks per second: 1000)


Obviously I got a significative performance boost from both paths just by moving FP divisions to the end and using release builds. Still, the loop version is almost 3 times faster (at least using MSVC 2008). Dunno if TCO isn't already being applied on this code, since apparently it's not using the stack at all (I tried other recursive algorithm and the the stack exploded with much smaller arrays).

I wonder if a recursion-oriented language+compiler like LISP or scheme would give better performance for the recursion option here. Passing functions, what a concept! So elegant.

From my personal experience, recursion is often easier to implement and understand in certain situations (traversing trees, sorting algorithms, etc.), but slower to execute than an iterative approach.

From my personal experience, recursion is often easier to implement and understand in certain situations (traversing trees, sorting algorithms, etc.), but slower to execute than an iterative approach.

Ditto.

Without obsessing about it past what spike said, any tail recursive function will be turned into a loop by a good compiler, after which point any speed differences are probably implementation differences. The obvious gain here is that in the loop you aren't pushing tons of overhead onto the stack. (Especially if you create a lot of temporary memory elements/objects inside each function). This is something that gets harped upon a lot around the time one takes Computer Science II course. (and gets further revisited later).

The conclusion I reached from college work, and observing the results in my own code is that spending the time to make your recursive function tail recursive is a very worth while investment of time. But once you can accomplish that there's no need to switch to a loop as the compiler should do that for you, and if it doesn't you probably aren't going to be happy about all the other things its not doing for you