Saturday, April 21, 2012

Recursive vs. For Loop, Which is better


Checked with factorial program and sequential sum.

In this blog post, I just wanted to post my observation on recursive and for loop program. I just started creating a factorial program using both recursive and for loop technique. I am just inquisitive to know which one is better.

In the initial observation both recursive and for loop produced results in almost identical time. 65 is the maximum integer value for which factorial is calculated properly. Then I did further power testing creating for loop to find out factorial for each integer starting 0 – 65 using both recursive and for loop technique. To my surprise I found out recursive did better than for loop by a few milliseconds.

Test case 1: Factorial
for (uint i = 0; i < 65; i++)
{
UInt64 factPower = FactForLoop(i);
}
for (uint i = 0; i < 65; i++)
{
UInt64 factPower = FactRecursive(i);
}

private UInt64 FactRecursive(UInt64 number)
{
if (number > 0)
fact = number * FactRecursive(number - 1);
return fact;
}
private UInt64 FactForLoop(UInt64 number)
{
for(uint i =1;i<=number;i++)
fact*=i;
return fact;
}

Then I tried sequential sum (i.e) for any given integer (n), the program does is creating a sum of integers starting 0 to n (0+1+2+..+n). In this case, the performance of both technique is identical and at some cases for loop fared better than the recursive technique opposite to what I saw earlier in factorial program.

Test Case 2: Sequential sum
//sum for loop
UInt64 result = SumForLoop(Convert.ToUInt64(txtBoxNumber.Text));
//sum recursive
UInt64 result = SumRecursive(Convert.ToUInt64(txtBoxNumber.Text));

private UInt64 SumRecursive(UInt64 number)
{
if (number > 0)
sum = number + SumRecursive(number - 1);
return sum;
}
private UInt64 SumForLoop(UInt64 number)
{
for (uint i = 1; i <= number; i++)
sum += i;
return sum;
}


Additional observation is that as we all know that the recursive call is being achieved by maintaining stack, it has its limits. At large number of stack calls (recursive calls), it may end up in stack overflow exception.

From my observation, you can go for recursive only if the number of stack calls is not huge otherwise stick to for loop. If you do find any other test results or different observation kindly let me know in the comments.

No comments:

Post a Comment