StackOverFlowException inside a recursive function

Question

I have a table in database as follows:

MenuItem
-------------
MenuItemId    1 --------+
MenuItemName            |
ParentId      * --------+

Now I have written a recursive function to get all the Parent MenuItems with their children.

private ICollection<MenuItem> GetAllChildrenOfSpecificMenuItemRecursively(MenuItem menuItem, IEnumerable<MenuItem> menuItems)
{
    ICollection<MenuItem>  Children = null;
    foreach (MenuItem mi in menuItems)
    {
        if (mi.ParentMenuItemId != null)
        {
            if (mi.ParentMenuItemId == menuItem.MenuItemId)
            {
                Children.Add(mi);
            }
            else
            {
                return GetAllChildrenOfSpecificMenuItemRecursively(mi, menuItems);
            }
        }
    }

    return Children;
}

Now, I am calling it from another function as follows:

public IEnumerable<MenuItem> GetAllParentMenuItemsWithChildren()
{
    List<MenuItem> MenuItems = new List<MenuItem>();
    IEnumerable<MenuItem> AllMenuItems = null;

    using (MaxContext entityContext = new MaxContext())
    {
        AllMenuItems = (from e in entityContext.MenuItemSet select e).ToList();

        foreach (MenuItem menuItem in entityContext.MenuItemSet)
        {
            if (menuItem.ParentMenuItemId == null)
            {
                menuItem.Children = GetAllChildrenOfSpecificMenuItemRecursively(menuItem, AllMenuItems);
                MenuItems.Add(menuItem);
            }
        }
    }

    return MenuItems;
}

But it gives me stackoverflowException inside the recursive function. I am sure that I am making a minor mistake in that function. Can anybody point out that mistake?

Mike Nakis · Accepted Answer · 2015-02-13 00:01:13Z

3

Your GetAllChildrenOfSpecificMenuItemRecursively() always recurses with mi. It should recurse with mi.ParentMenuItemId instead.

answered Feb 13, 2015 at 0:01

Mike Nakis

63k11 gold badges128 silver badges173 bronze badges

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

3 Comments

Vishal Over a year ago

But I am not having a parameter of type int to recurse with mi.ParentMenuItemId......

Mike Nakis Over a year ago

Well, I do not know, you need to somehow find it. One thing is sure: always recursing with 'mi' will result in stack overflow. You wanted someone to point out your mistake, so, that's it.

Vishal Over a year ago

Ok. Thanks for your answer. I will try it and if I find any trouble then I will ask you.

Michal Ciechan · Accepted Answer · 2015-02-13 00:40:56Z

1

I think there is a simpler (and maybe faster) way of doing this without using recursion. Something like this:

    public ICollection<MenuItem> GetMenuItemsAsTreeList()
    {
        AllMenuItems = entityContext.MenuItemSet.ToList();

        Dictionary<int, MenuItem> dic = AllMenuItems.ToDictionary(n => n.Id, n => n);

        List<MenuItem> rootMenuItems = new List<MenuItem>();

        foreach (MenuItem menuItem in AllMenuItems)
        {
            if (menuItem.ParentMenuItemId.HasValue)
            {
                MenuItem parent = dic[menuItem.ParentMenuItemId.Value];
                menuItem.ParentMenuItem = parent;
                parent.SubMenuItems.Add(menuItem);
            }
            else
            {
                rootMenuItems.Add(menuItem);
            }
        }

        return rootMenuItems;
    }

edited Feb 13, 2015 at 0:40

Michal Ciechan

13.9k12 gold badges81 silver badges123 bronze badges

answered Feb 13, 2015 at 0:39

Augusto Barreto

3,6964 gold badges34 silver badges42 bronze badges

2 Comments

Vishal Over a year ago

Thanks. That's a really great answer. Now I learned how to make recursive structure from data.

Augusto Barreto Over a year ago

I’m glad I was able to help.

Michal Ciechan · Accepted Answer · 2015-02-13 00:38:13Z

1

Why are you always passing the same menuItems colleciton into recursive function?

your code should be something along the lines of:

private IEnumerable<MenuItem> GetAllChildrenOfSpecificMenuItemRecursively(MenuItem menuItem)
{
    var children = new List<MenuItem>();
    foreach (MenuItem mi in menuItem.Children)
    { 
        // Why are you checking this?
        if (mi.ParentMenuItemId != null)
        {
            // Why are you checking this?
            if (mi.ParentMenuItemId == menuItem.MenuItemId)
            {
                children.Add(mi);
            }
            else
            {

                children.AddRange(GetAllChildrenOfSpecificMenuItemRecursively(mi))
            }
        }
    }

    return Children;
}

From method name, this is all that it should be doing:

private IEnumerable<MenuItem> GetAllChildrenOfSpecificMenuItemRecursively(MenuItem menuItem)
{
    var children = new List<MenuItem>();
    if (menuItem.Children == null) return children;

    foreach (MenuItem mi in menuItem.Children)
    { 
       children.Add(mi);
       children.AddRange(GetAllChildrenOfSpecificMenuItemRecursively(mi));       
    }

    return Children;
}

Edit:

public class MenuItem
{
    [DatabaseGenerated(DatabaseGeneratedOption.Identity)]
    public int Id { get; set; }
    public string Name { get; set; }
    public int ParentId { get; set; }

    public virtual MenuItem Parent { get; set; }

    [InverseProperty("Parent")]
    public virtual ICollection<MenuItem> Children { get; set; }
}

edited Feb 13, 2015 at 0:38

answered Feb 13, 2015 at 0:24

Michal Ciechan

13.9k12 gold badges81 silver badges123 bronze badges

6 Comments

Vishal Over a year ago

Sorry, if I am wrong, but I think you are completely misunderstanding me. Suppose I have 10 menuItems in my database table. Now I want to create a hierarchical structure using MenuItemId and ParentId.

Michal Ciechan Over a year ago

Why not use navigation properties, or a custom property on your entity to simplify? Are you using EF?

Vishal Over a year ago

Yes I am using Entity Framework, but I am trying to learn code-first approach.

Michal Ciechan Over a year ago

see Edit on how you Entity should look so the entity takes care of getting its children.

Vishal Over a year ago

OK, I will try it and let you know. Thanks for the help.

|

Collectives™ on Stack Overflow

StackOverFlowException inside a recursive function

3 Answers 3

3 Comments

2 Comments

6 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

2 Comments

6 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related