Forum

loops versus recursion

Discuss programming topics for any language, any source base. If it is programming related but doesn't fit in one of the below categories, it goes here.

Moderator: InsideQC Admins

loops versus recursion

Postby frag.machine » 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:
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;
}


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.
Last edited by frag.machine on Sun Apr 28, 2013 5:49 pm, edited 1 time in total.
I know FrikaC made a cgi-bin version of the quakec interpreter once and wrote part of his website in QuakeC :) (LordHavoc)
User avatar
frag.machine
 
Posts: 2069
Joined: Sat Nov 25, 2006 1:49 pm

Re: loops versus recursion

Postby Spike » Sun Apr 28, 2013 5:27 pm

try a compiler that has decent tail recursion optimisations, so that it compiles it into a loop instead of actually recursing. :P
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).
Spike
 
Posts: 2883
Joined: Fri Nov 05, 2004 3:12 am
Location: UK

Re: loops versus recursion

Postby frag.machine » Sun Apr 28, 2013 6:02 pm

Spike wrote:try a compiler that has decent tail recursion optimisations, so that it compiles it into a loop instead of actually recursing. :P
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. :P

Well, thanks for confirming what I already suspected. :D
I know FrikaC made a cgi-bin version of the quakec interpreter once and wrote part of his website in QuakeC :) (LordHavoc)
User avatar
frag.machine
 
Posts: 2069
Joined: Sat Nov 25, 2006 1:49 pm

Re: loops versus recursion

Postby frag.machine » Sun Apr 28, 2013 6:34 pm

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

Code: Select all
/**
 * 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: Select all
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 know FrikaC made a cgi-bin version of the quakec interpreter once and wrote part of his website in QuakeC :) (LordHavoc)
User avatar
frag.machine
 
Posts: 2069
Joined: Sat Nov 25, 2006 1:49 pm

Re: loops versus recursion

Postby qbism » Mon Apr 29, 2013 3:53 am

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.
User avatar
qbism
 
Posts: 1235
Joined: Thu Nov 04, 2004 5:51 am

Re: loops versus recursion

Postby jitspoe » Mon Apr 29, 2013 4:14 pm

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.
jitspoe
 
Posts: 217
Joined: Mon Jan 17, 2005 5:27 am

Re: loops versus recursion

Postby frag.machine » Mon Apr 29, 2013 5:38 pm

jitspoe wrote: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.
I know FrikaC made a cgi-bin version of the quakec interpreter once and wrote part of his website in QuakeC :) (LordHavoc)
User avatar
frag.machine
 
Posts: 2069
Joined: Sat Nov 25, 2006 1:49 pm

Re: loops versus recursion

Postby WickedShell » Tue Apr 30, 2013 6:48 pm

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 :)
WickedShell
 
Posts: 24
Joined: Mon Feb 14, 2011 5:16 am


Return to General Programming

Who is online

Users browsing this forum: No registered users and 1 guest