recursive function call in foreach throwing system.stackoverflowexception

Question

I am getting a System.StackOverflowException: 'Exception of type 'System.StackOverflowException' was thrown.' message.

My code as follows, Here I want to assign value to a variable recursively based on the condition and return the list.

public class FancyTree
{
    public string title { get; set; }
    public string key { get; set; }     
    public List<FancyTree> children { get; set; }
}

For example the FancyTree Class produces the output like parent->child or parent->parent->child or parent->parent->parent->child just like the Treeview structure.

public JsonResult EmployeesTree()
{  
   var output = converttoFancyTree(db.Database.GetEmployees(true));
   return Json(output, JsonRequestBehavior.AllowGet);
}
public List<FancyTree> converttoFancyTree(List<EmpTable> emps)
    {
        var output = new List<FancyTree>();
        foreach (var emp in emps)
        {
            var fancyTreeItem = new FancyTree();
            fancyTreeItem.key = emp.EMP_ID.ToString();
            fancyTreeItem.title = emp.EMP_NAME;

            if (!string.IsNullOrEmpty(emp.TEAM))
                {
                    //var empIDs = emp.TEAM?.Split(',')?.Select(Int32.Parse)?.ToList();
                    var tms = emp.TEAM.Split(',');
                    if (tms.Length > 0) {
                        var empIDs = new List<int>();
                        foreach (var t in tms) 
                        {
                            empIDs.Add(int.Parse(t));
                        }
                        var TeamMembers = emps.Where(x => empIDs.Contains(x.EMP_ID)).ToList();
                        if (TeamMembers.Count > 0)
                        {
                            var childrens = converttoFancyTree(TeamMembers);
                            fancyTreeItem.children = childrens;
                        }   
                    }                        
                }
            output.Add(fancyTreeItem);
        }
        return output;
    }

Your logic is broken. Look at how you select the items for the tms and TeamMembers collections. Once you enter the very first recursion with a non-empty local TeamMembers collection, the recursively generated local TeamMembers collections can never become an empty collection anymore, leading to an infinite recursion, i.e. stack overflow. Note that your problem is not with the FancyTree class, as your question seems to suggest. That class is entirely innocent. It's your EmployeesTree method and how it processes List<EmpTable>. — user19858830
– user19858830, Commented Sep 27, 2022 at 13:29
@MySkullCaveIsADarkPlace I changed the select items logic for tms and updated my question. Still it throwing the stack overflow exception? — sridharnetha
– sridharnetha, Commented Sep 27, 2022 at 13:51
It seems async await Task may solve the stackoverflowexception. Let's try. — sridharnetha
– sridharnetha, Commented Sep 27, 2022 at 13:57
There is no way to infinite recursion when conditions added. — sridharnetha
– sridharnetha, Commented Sep 27, 2022 at 14:02
"There is no way to infinite recursion when conditions added." Alright, this means there is no chance for a StackOverflowException. Problem solved, i guess... — user19858830
– user19858830, Commented Sep 27, 2022 at 14:03

JonasH · Accepted Answer · 2022-09-28 11:29:34Z

1

I would assume your input is in the form of a plain list of objects, where each object contains the IDs of all the children, and you want to convert this to an object representation, i.e. something like:

public class Employee{
    public int Id {get;}
    public List<int> SubordinateIds {get;}
}

public class EmployeeTreeNode{
    public IReadOnlyList<EmployeeTreeNode> Subordinates {get;} ;
    public int Id {get;}
    public EmployeeTreeNode(int id, IEnumerable<EmployeeTreeNode> subordinates){
        Id = id;
        Subordinates = subordinates;
}

To convert this to a tree representation we can start by finding the roots of the tree, i.e. employees that are not subordinate to anyone.

var allSubordinates = allEmployees.SelectMany(e => e.SubordinateIds).ToList();
var allRoots = allEmployees.Select(e => e.Id).Except(allSubordinates);

We then need an efficient way to find a specific employee by the Id, i.e. a dictionary:

var employeeById = allEmployees.ToDictionary(e => e.Id, e => e.SubordinateIds);

We can then finally do the actual recursion, and we can create a generic helper method to assist:

public static TResult MapChildren<T, TResult>(
    T root, 
    Func<T, IEnumerable<T>> getChildren,
    Func<T,  IEnumerable<TResult>, TResult> map)
{
    return RecurseBody(root);
    TResult RecurseBody(T item) => map(item,  getChildren(item).Select(RecurseBody));
}
...

var tree = allRoots.Select(r => MapChildren(
    r, 
    id => employeeById[id], 
    (id, subordinates) => new EmployeeTreeNode(id, subordinates)));

This will recurse down to any employee without any subordinates, create EmployeeTreeNode for these, and then eventually traverse up the tree, creating node objects as it goes.

This assumes that there are no loops/cycles. If that is the case you do not have a tree, since trees are by definition acyclic, and the code will crash. You will instead need to handle the more general case of a graph, and this is a harder problem, and you will need to decide how the cycles should be handled.

edited Sep 28, 2022 at 11:29

answered Sep 27, 2022 at 14:29

JonasH

39k2 gold badges16 silver badges33 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Luke Over a year ago

"If that is the case you actually have a graph, and the code will crash" minor semantic issue: a tree is a graph. Maybe you mean a cyclic graph here?

JonasH Over a year ago

@Luke good point, I hope my edit makes it clearer.

Collectives™ on Stack Overflow

recursive function call in foreach throwing system.stackoverflowexception

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related