Monday, November 19, 2007

I decided to write this entry after seeing an article in codeproject describing the "disadvantage" of recursion. I won't put a link to the article because it's not an article worthy of reading, too much programming "don't dos".

Lets take for example the common use (i.e. the one every computer class use) calculating n!

the for loop looks like:

res = 1;
for(i=1;i<=n;i++) {
res *= i;
}


and the function looks like:

function calc(int n)
{
if (n>1) {
return calc(n-1)*n;
} else {
return 1;
}
}

The function will have to assign a new space for n in each iteration. That's a time consuming operation, but if I'll write the function:

function calc(ref int n)
{
if (n>1) {
return n*calc(--n);
} else {
return 1;
}
}

it would work faster, though no one would have the ability to decipher this call...

It looks like a loop is better than recursion because of the stack assignments, but that's incorrect. Basically it's a question of what's more appropriate for the problem at hand.
A loop is easier to handle for as long as it's a "short" calculation, by short I mean the number of lines. A recursive function is better for the cases where the operation is complicated, or if there are memory allocations you have to clear within the operation (in the .NET one can use GC.Collect(), but other languages don't have such a mechanism.)

Summarizing this article in one line:
You're a programmer, THINK BEFORE WRITING CODE!

No comments: