Recursion and stackoverflow

Question

I have class like

 public class Question
    {
        private readonly int questionID;
                private List<Question> similarquestions; // Similarity is bidirectional
}

to get all the nested classes I use recursion using method like

public static IEnumerable<T> Traversal<T>(
    T root,
    Func<T, IEnumerable<T>> getChildren)
{
    if (root == null)
    {
        yield break;
    }

    yield return root;

    var children = getChildren(root);
    if (children == null)
    {
        yield break;
    }

    foreach (var child in children)
    {
        foreach (var node in Traversal(child, getChildren))
        {
            yield return node;
        }
    }
}

I use it like

var  classes = Traversal(movie, x => x.similarquestions)

but it give stackoverflow Exception any idea how to fix that please

Run it in the debugger and see if the recursion is actually working. — D Stanley
– D Stanley, Commented Feb 4, 2015 at 19:57
If Questions point to each other then this will never terminate. — 500 - Internal Server Error
– 500 - Internal Server Error, Commented Feb 4, 2015 at 19:59
Keep a list of questions already traversed and do not process them again. — D Stanley
– D Stanley, Commented Feb 4, 2015 at 20:01

BradleyDotNET · Accepted Answer · 2015-02-04 20:08:34Z

Since similarity is bi-directional, you need to keep a "visited" list and check against it:

List<Question> visited = new List<Question>();

public static IEnumerable<T> Traversal<T>(
    T root,
    Func<T, IEnumerable<T>> getChildren)
{
    if (root == null)
    {
        yield break;
    }

    //We visited this node!
    visited.Add(root);

    yield return root;

    var children = getChildren(root);
    if (children == null)
    {
        yield break;
    }

    //Don't re-visit nodes we have seen before!
    foreach (var child in children.Except(visited))
    {
        foreach (var node in Traversal(child, getChildren))
        {
            yield return node;
        }
    }
}

There are other ways to check against the visited list as well, but this will give you an idea of how to do it. Also, if this is being called multiple times, be sure to clear/instantiate the list before starting a new traversal!

Collectives™ on Stack Overflow

Recursion and stackoverflow

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related