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.
Post Reply
frag.machine
Posts: 2126
Joined: Sat Nov 25, 2006 1:49 pm

loops versus recursion

Post by frag.machine »

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)
Spike
Posts: 2914
Joined: Fri Nov 05, 2004 3:12 am
Location: UK
Contact:

Re: loops versus recursion

Post by Spike »

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).
frag.machine
Posts: 2126
Joined: Sat Nov 25, 2006 1:49 pm

Re: loops versus recursion

Post by frag.machine »

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)
frag.machine
Posts: 2126
Joined: Sat Nov 25, 2006 1:49 pm

Re: loops versus recursion

Post by frag.machine »

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)
qbism
Posts: 1236
Joined: Thu Nov 04, 2004 5:51 am
Contact:

Re: loops versus recursion

Post by qbism »

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

Re: loops versus recursion

Post by jitspoe »

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.
frag.machine
Posts: 2126
Joined: Sat Nov 25, 2006 1:49 pm

Re: loops versus recursion

Post by frag.machine »

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

Re: loops versus recursion

Post by WickedShell »

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 :)
Post Reply