Click here to Skip to main content
15,113,057 members
Articles / Programming Languages / C#
Tip/Trick
Posted 22 Jun 2015

Tagged as

Stats

45.1K views
80 downloads
10 bookmarked

Recursive function vs. Loop

Rate me:
Please Sign up or sign in to vote.
4.72/5 (16 votes)
22 Jun 2015CPOL2 min read
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.

Image 1

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>();
            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 20th, 2015: Initial version

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Mostafa A. Ali
Engineer
Canada Canada
Programming for me is a hobby

Comments and Discussions

 
AnswerDifference Pin
prashantglobe12-May-19 22:22
Memberprashantglobe12-May-19 22:22 
GeneralMy vote of 5 Pin
David A. Gray28-Jun-15 16:21
MemberDavid A. Gray28-Jun-15 16:21 
GeneralRe: My vote of 5 Pin
Mostafa A. Ali1-Jul-15 16:08
professionalMostafa A. Ali1-Jul-15 16:08 
GeneralRe: My vote of 5 Pin
David A. Gray2-Jul-15 10:33
MemberDavid A. Gray2-Jul-15 10:33 
GeneralRe: My vote of 5 Pin
Mostafa A. Ali2-Jul-15 11:40
professionalMostafa A. Ali2-Jul-15 11:40 
GeneralRe: My vote of 5 Pin
David A. Gray2-Jul-15 13:41
MemberDavid A. Gray2-Jul-15 13:41 
AnswerRe: My vote of 5 Pin
Liju Sankar17-Jul-15 7:05
professionalLiju Sankar17-Jul-15 7:05 
GeneralRe: My vote of 5 Pin
Mostafa A. Ali17-Jul-15 17:46
professionalMostafa A. Ali17-Jul-15 17:46 
GeneralMy vote of 5 Pin
Saravanan21124-Jun-15 19:07
professionalSaravanan21124-Jun-15 19:07 
GeneralRe: My vote of 5 Pin
Mostafa A. Ali24-Jun-15 20:48
professionalMostafa A. Ali24-Jun-15 20:48 
QuestionReasons for loop is better Pin
asdfyfsdg24-Jun-15 15:59
professionalasdfyfsdg24-Jun-15 15:59 
AnswerRe: Reasons for loop is better Pin
Mostafa A. Ali24-Jun-15 18:25
professionalMostafa A. Ali24-Jun-15 18:25 
QuestionMy vote of "needs improvement" Pin
DavidJDriver24-Jun-15 14:38
MemberDavidJDriver24-Jun-15 14:38 
AnswerRe: My vote of "needs improvement" Pin
Mostafa A. Ali24-Jun-15 18:16
professionalMostafa A. Ali24-Jun-15 18:16 
GeneralMy vote of 5 Pin
EiadXP23-Jun-15 3:08
professionalEiadXP23-Jun-15 3:08 
GeneralRe: My vote of 5 Pin
Mostafa A. Ali23-Jun-15 9:15
professionalMostafa A. Ali23-Jun-15 9:15 
GeneralMy vote of 5 Pin
Member 1142813723-Jun-15 0:25
MemberMember 1142813723-Jun-15 0:25 
GeneralRe: My vote of 5 Pin
Mostafa A. Ali23-Jun-15 9:15
professionalMostafa A. Ali23-Jun-15 9:15 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.