loops versus recursion
Posted: Sun Apr 28, 2013 4:54 pm
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:
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.
So, I decided to write a simple, näive code snippet to verify and take my own conclusions. Here it follows:
Code: Select all
/**
* 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;
}
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.