Recursive function vs. Loop

• Download LineSegment.7z - 7.2 MB
• Download RecursiveLoopComparison-noexe.zip - 61.2 KB
• Download RecursiveLoopComparison.zip - 61.2 KB

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).

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.

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

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

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>();
            seen.Add(item);
            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))
                    {
                        seen.Add(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 20^th, 2015: Initial version