Iteration or recursion?

An interesting question came up… if you have to calculate the factorial of a number, how would you do it? As you know, the formula is simple:

rec1

My first thought was a recursive function:

public static int CalculateFactorialRecursive(int number)
{
if (number <= 1) return 1;
return number* CalculateFactorialRecursive (number - 1);
}

And an alternative would be a for loop:

public static int CalculateFactorialForLoop(int number)
{
var product = 1;
for (var counter = number; counter > 1; counter--)
{
product *= counter;
}
return product;
}

The question is: what method do you prefer?

Obviously the version that uses iteration is a lot easier to understand; and because I like simplicity it would probably be the best candidate. But what about performance? Doesn’t recursion also imply more overhead?

I created a small test that calculates the factorial of 1000 one million times; and the average duration for the recursive method was around 7300 ms:

rec2

The same test but this time using the iteration method was clearly faster:

rec3

So recursion is next to being hard to read also much slower. The reason is that each function call has to pop return value from the stack and push arguments on the stack, and also creates a stack frame (with information about the stack). All these operations take time. Also, you risk a stack overflow exception if too many stack frames are created (it is limited in size). And finally, because each call is accessing different parts of the memory, it hurts cache locality, which also means another slowdown.

Sure, if you only calculate one factorial, performance is not an issue. But in general, a more complex recursive function has more impact and performance may become a bottleneck.

Conclusion: only use recursion if it’s a natural solution for your problem and if performance doesn’t get hurt. In our example, we know in advance the number of iterations so we don’t need to use recursion; instead we can use a simple iteration that is much clearer to read and gives best performance.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s