CODEWITHSUNDEEP
c#recursioniterationstack-overflow
Mr. 笑哥
Mr. 笑哥

Reputation: 283

C# Traverse Hierarchy without Recursion

I need a hand to transform my recursive function into a loop as I'm stuck trying to do this for hours. The reason is that I kept running into StackOverflow exception.

Please check the following code:

private List<int> GetManagers(Employee employee, List<Employee> employeeList)
{
    List<int> collection = new List<int>();
    if (employee.DirectManagers.Any())
    {
        var managers = employeeList.Where(x => employee.DirectManagers.Any(y => y.Equals(x.Id)));
        foreach (var manager in managers)
        {
            if (!collection.Any(x => x.Equals(manager.Id)))
                collection.Add(manager.Id);
            if (manager.DirectManagers.Any())
                collection.AddRange(GetManagers(manager, employeeList));
        }
    }

    return collection;
}

Edit: More codes here

foreach (var employee in employeeList)
{
    List<int> allManagers = new List<int>();
    allManagers = GetManagers(employee, employeeList);

    // Do something with allManagers found here that does not affect the collection
}

public class Employee
{
    public int Id { get; set; }
    public int? DepartmentId { get; set; }
    public List<int> DirectManagers { get; set; }
    public List<int> DirectSubordinates { get; set; }
    public int Counter { get; set; }
}

    var employeeList = context.AdministratorProfiles
        .Where(x => !x.dateResigned.HasValue && x.departmentID.HasValue)
        .Select(x => new Employee {
            Id = x.id,
            DepartmentId = x.departmentID,
            Counter = 0,
            DirectManagers = x.Managers.Select(y => y.managerID).ToList(),
            DirectSubordinates = x.Subordinates.Select(y => y.adminID).ToList()
        }).ToList(); // TODO: Add active account here

Basically, what this does is that I'm trying to get all the managers of an Employee. Due to the huge number of staff, I often run into StackOverflow exception. I need a hand, appreciate if anyone out there could lend a hand. Thank you.

Edit: Now, I have listed all the codes. So perhaps you can have a better understanding. Basically, what I'm trying to do is to loop through every single employee to perform work, first I must have a work list. This work list would exclude all the managers or managers' managers to form the final list.

Upvotes: 0

Views: 635

Answers (2)

Kirill Bestemyanov
Kirill Bestemyanov

Reputation: 11964

Your problem is not recursion but cyclic references. You can use pattern visitor to work with this problem. (In this pattern you mark all entities that were visited with your recursion method and if you visit this entity again, you just return)

Upvotes: 2

Max Hampton
Max Hampton

Reputation: 1304

You could do something like:

...
Dictionary<int, bool> processed = new Dictionary<int, bool>();
Queue<Employee> managersQueue = new Queue<Employee>();
managersQueue.Enqueue(employee);

while (managersQueue.Any())
{
    var currentEmployee = stack.Dequeue();
    var managers = employeeList.Where(x => currentEmployee.DirectManagers.Any(y => y.Equals(x.Id)));
    foreach (var manager in managers)
    {
        if (processed.ContainsKey(manager.Id)) continue;
        processed.Add(manager.Id, true);
        managersQueue.Enqueue(manager);
    }
}
return processed.Select(x => x.Key).ToList();

This is just a basic outline of how you could do this iteratively, obviously I don't know your code base or exactly how certain calls would be made.

Upvotes: 0

Related Questions