15,745,746 members
Articles / Programming Languages / C#
Tip/Trick
Posted 22 Jun 2015

51.9K views
10 bookmarked

# Recursive function vs. Loop

Rate me:
A simple insight into the difference between recursive functions and loops

## Introduction

Recursive function is a function that calls itself, for me it is a fascinating way to do relatively complex task with few lines of code; for example the factorial can be calculated using this recursive function (for simplicity, I didn't check for negative input).

C#
```static private double FactorialRecursive(int n)
{
if (n == 1)
{
return 1;
}
return n * FactorialRecursive(n - 1);
}```

Here, we added a condition if n == 1 to stop the loop while any number (n) bigger than 1 will call the function for (n-1); which means if n = 5, the result will be 5*4*3*2*1.

On the other hand, a loop can be used to do exactly the same as following.

C#
```static private double FactorialLoop(int n)
{
double result = 1;
while (n > 1)
{
result *= n--;
}
return result;
}```

The attached code is a simple comparison (computation time) between the two methods which shows that the loop is faster by around 40%; but who cares when the difference is a tiny fraction of the seconds. However, sometimes recursive function fails miserably as shown in the following sections.

## Background

I worked recently with a geometry project related to processing lines. Our start point was a database that has two tables; the first table stores line segments while the second tables stores the intersections between these segments as shown in the following picture.

Figure 1: a very simplified version of the database

## Using the code

Here I am trying to group these segments into different lines based on the intersection table. Simply I will select one segment and add it to a line, then I will grab all touching segments and add them; repeat these steps till I exhaust the line series. Afterwards, I will select the next unprocessed line segments to form the second line so forth.

This can be accomplished using recursive function as following

C#
```private static void GroupLineRecursive()
{
try
{
Console.WriteLine("Constructing line using recursive function...");
using (var db = new SegmentsEntities())
{
int lineNumber = 1001;
foreach (var segment in db.tblSegments)
{
if (segment.LineName == null)
{
RecursiveCall(segment, lineNumber);
lineNumber++;
}
}
Console.WriteLine("Displaying results for recursive function");
//NOTE: we have to use local because we didn't save changes to DB
var result = db.tblSegments.Local.GroupBy(a => a.LineName); //Method syntax

//Query syntax
//var result = from segment in db.tblSegments.Local
//             group segment by segment.LineName into newGroup
//             select newGroup;
foreach (var group in result)
{
Console.WriteLine("Line #{0}", group.Key);
foreach (var item in group)
{
Console.WriteLine("\tSegment #{0}", item.SegmentName);
}
}
}
}
catch (Exception ex)
{
Console.WriteLine(ex.Message);
}
}

private static void RecursiveCall(tblSegment segment, int lineNumber)
{
Console.WriteLine("Processing item #{0}", segment.Id);
segment.LineName = lineNumber.ToString();
var unprocessed = from b in segment.tblIntersections
where b.tblSegment1.LineName == null
select b.tblSegment1;
foreach (var item in unprocessed)
{
RecursiveCall(item, lineNumber);
}
}
```

Although the aforementioned code will yield the right results; it will throw `StackOverflowException` if you have relatively long line (say around 30,000 line segments). The exception is thrown because C#  (beside C++, python) does not optimize tail-recursion (when the last line is the self-call).

In order to overcome this problem, we should use loop function to accomplish the same results as following.

Note: This code has been adopted from Eric Lippert's Blog

C#
```private static void GroupLineLoop()
{
try
{
Console.WriteLine("Constructing line using Loop function...");
using (var db = new SegmentsEntities())
{
int lineNumber = 1001;
foreach (var segment in db.tblSegments)
{
if (segment.LineName == null)
{
foreach (var item in LoopCall(segment))
{
item.LineName = lineNumber.ToString();
}
lineNumber++;
}
}
Console.WriteLine("Displaying results for loop function");
//NOTE: we have to use local because we didn't save changes to DB
var result = db.tblSegments.Local.GroupBy(a => a.LineName); //Method syntax

//Query syntax
//var result = from segment in db.tblSegments.Local
//             group segment by segment.LineName into newGroup
//             select newGroup;
foreach (var group in result)
{
Console.WriteLine("Line #{0}", group.Key);
foreach (var item in group)
{
Console.WriteLine("\tSegment #{0}", item.SegmentName);
}
}
}
}
catch (Exception ex)
{
Console.WriteLine(ex.Message);
}
}

private static IEnumerable<tblSegment> LoopCall(tblSegment item)
{
var seen = new HashSet<tblSegment>();
var stack = new Stack<tblSegment>();
stack.Push(item);
yield return item;
while (stack.Count > 0)
{
tblSegment current = stack.Pop();
Console.WriteLine("Processing item #{0}", current.Id);
var unprocessed = from b in current.tblIntersections
where b.tblSegment1.LineName == null
select b.tblSegment1;
foreach (tblSegment newItem in unprocessed)
{
if (!seen.Contains(newItem))
{
stack.Push(newItem);
yield return newItem;
}
}
}
}```

Here `Stack` has been used to collect all segments before assign them to a line; I tested this code with 50,000+ segments and it works flawlessly.

## Conclusion

Although recursive function might be appealing, try as much as you can to avoid it. Loops can replace recursive function in all cases but it is faster and more robust.

## History

• June 20th, 2015: Initial version

Written By
Engineer
Programming for me is a hobby

 First Prev Next
 Difference prashantglobe12-May-19 21:22 prashantglobe 12-May-19 21:22
 My vote of 5 David A. Gray28-Jun-15 15:21 David A. Gray 28-Jun-15 15:21
 Re: My vote of 5 Mostafa A. Ali1-Jul-15 15:08 Mostafa A. Ali 1-Jul-15 15:08
 Re: My vote of 5 David A. Gray2-Jul-15 9:33 David A. Gray 2-Jul-15 9:33
 Re: My vote of 5 Mostafa A. Ali2-Jul-15 10:40 Mostafa A. Ali 2-Jul-15 10:40
 Re: My vote of 5 David A. Gray2-Jul-15 12:41 David A. Gray 2-Jul-15 12:41
 Re: My vote of 5 Liju Sankar17-Jul-15 6:05 Liju Sankar 17-Jul-15 6:05
 Re: My vote of 5 Mostafa A. Ali17-Jul-15 16:46 Mostafa A. Ali 17-Jul-15 16:46
 My vote of 5 Saravanan21124-Jun-15 18:07 Saravanan211 24-Jun-15 18:07
 Re: My vote of 5 Mostafa A. Ali24-Jun-15 19:48 Mostafa A. Ali 24-Jun-15 19:48
 Reasons for loop is better asdfyfsdg24-Jun-15 14:59 asdfyfsdg 24-Jun-15 14:59
 Re: Reasons for loop is better Mostafa A. Ali24-Jun-15 17:25 Mostafa A. Ali 24-Jun-15 17:25
 My vote of "needs improvement" DavidJDriver24-Jun-15 13:38 DavidJDriver 24-Jun-15 13:38
 Re: My vote of "needs improvement" Mostafa A. Ali24-Jun-15 17:16 Mostafa A. Ali 24-Jun-15 17:16