CODEWITHSUNDEEP
c#.netrecursion
Trexx
Trexx

Reputation: 95

StackoverflowException recursion and slow execution

I have this code

private static void Count(List<DataRowSet> rows, int id, ref int count)
{
    foreach (DataRowSet row in rows) {
        if (row.parentId == id) {
            count++;

            Count(rows, row.Id, ref count);
        }
    }
}

and this class

public class DataRowSet
{
    public int Id;
    public int parentId;

    public DataRowSet(int id, int parent)
    {
        this.Id = id;
        this.parentId = parent;
    }
}

I want to count every child of a List<DataRowSet> with a specific id.

Count(dataList, 1, ref cnt);

That works but once I have more than 8000 entries in dataList a StackOverflow exception happens. Also the code is slow, it takes about 1.5 seconds to find all entries.

What do I do to fix that?

Upvotes: 2

Views: 157

Answers (1)

devsmn
devsmn

Reputation: 1040

The StackOverflowException happens because your recursion is too deep. It works fine up to 8000, everything above is simply too much for the stack. You can solve this by using a Stack<DataRowSet> and pushing items into it instead of recursively calling the function.

Looking at your DataRowSet class it seems like it's a flat list so there's a simple way to improve the performance by using a ILookup<int, DataRowSet>. That way - instead of iterating over the list over and over again - you can use the key to find any related items.

First you'll have to push the top-level items on your stack. This can be done like this.

Stack<DataRowSet> stack = new Stack<DataRowSet>(
    dataRows.Where(x => x.Id == id));

Using dataRows.ToLookup, you can group the entries by their ParentId.

ILookup<int, DataRowSet> dataLookup = dataRows.ToLookup(x => x.parentId);

After that you just have to loop through stack until it's empty while pushing new items that have the correct id.

while (stack.Count > 0) {
    DataRowSet currentRow = stack.Pop();

    foreach (DataRowSet rowSet in dataLookup[currentRow.Id]) {
        stack.Push(rowSet);
    }
}

That way you don't have to worry about the StackOverflowException again and the performance has been increased as well.

All together your new function will look somewhat like this.

private static int Count(List<DataRowSet> dataRows, int id)
{
    int totalDescendants = 0;

    Stack<DataRowSet> stack = new Stack<DataRowSet>(
        dataRows.Where(x => x.Id == id));

    ILookup<int, DataRowSet> dataLookup = dataRows.ToLookup(x => x.parentId);

    while (stack.Count > 0) {
        DataRowSet currentRow = stack.Pop();

        foreach (DataRowSet rowSet in dataLookup[currentRow.Id]) {
            totalDescendants++;
            stack.Push(rowSet);
        }
    }

    return totalDescendants;

}

and can be called like this

int cnt = Count(dataList, 1);

Upvotes: 7

Related Questions