Переполнение стека при рекурсии c#

Question

Всем привет! Пишу метод, которые будет проходится по графу depth-first методом. Вот мой код:

 public static IEnumerable<T> DepthTraversalTree<T>(ITreeNode<T> root)
        {
            List<T> list = new List<T>();
            if ((int)Convert.ChangeType(root.Data, typeof(int)) == 99999)
                return list;
            list.Add(root.Data);
            if (!(root.Children == null))
                foreach (var item in root.Children)
                {
                    list.Add(item.Data);
                    if (!(item.Children == null))
                    {
                        var s = DepthTraversalTree(item);
                        for (int i = 1; i < s.Count(); i++)
                        {
                            list.Add(s.ToArray()[i]);
                        }
                    }
                }
            return list;
        }

Не большие графы проходит без проблем. Но когда я отправляю граф на 100000 записей в глубину, выбрасывает Stackoverflow исключение. Буду благодарен за любую помощь)

Answer 1

Стек - штука небольшая, не нужно засовывать в него такую кучу списков. Со стеком надо бережно.

Список у вас сквозной, так что можно использовать его по ссылке, а создать один раз.

public static IEnumerable<T> DepthTraversalTree<T>(ITreeNode<T> root)
{
    List<T> list = new List<T> { root.Data };
    if (root.Children?.Count > 0)
    {
        DepthTraversalTree(root, list);
    }
    return list;
}

private static void DepthTraversalTree<T>(ITreeNode<T> node, List<T> list)
{
    if ((int)Convert.ChangeType(node.Data, typeof(int)) == 99999)
        return;

    foreach (var item in node.Children)
    {
        list.Add(item.Data);
        if (item.Children?.Count > 0)
        {
            DepthTraversalTree(item, list);
        }
    }
}

БЛОГ НА HUSL

Переполнение стека при рекурсии c#

Ответы (1 шт):