Предотвратить «Процесс завершен из-за исключения StackOverflowException» в C#

Question

У меня есть программа, которая строит очень большое дерево из входных данных и проходит по нему рекурсией. Я протестировал программу на меньших входных данных (и, следовательно, на меньших деревьях), и она работает так, как задумано. Однако, когда входные данные намного больше, я сталкиваюсь с тем, что «Процесс завершен из-за исключения StackOverflowException». Я предполагаю, что это связано с нехваткой места в стеке. Есть ли способ предотвратить это или мне нужно вместо этого перейти на построение дерева с помощью итераций? Или, может быть, я где-то упускаю случай бесконечной рекурсии?

Вот код:

class Program
    {
        static int[] tileColors;
        static Color[] colors;
        static int totalTiles;
        static void Main(string[] args)
        {
            Stopwatch s = new Stopwatch();
            s.Start();

            string[] data = File.ReadAllLines("colors.txt");
            totalTiles = int.Parse(data[0].Split(' ')[0]);
            int totalColors = int.Parse(data[0].Split(' ')[1]);

            string[] colorsRaw = data[1].Split(' ');
            tileColors = new int[totalTiles];
            for (int i = 0; i < totalTiles; i++)
            {
                tileColors[i] = int.Parse(colorsRaw[i]) - 1;
            }

            colors = new Color[totalColors];
            for (int i = 3; i < data.Length; i++)
            {
                string[] raw = data[i].Split(' ');
                int[] pair = new int[] { int.Parse(raw[0]) - 1, int.Parse(raw[1]) - 1 };

                if (colors[pair[0]] == null)
                    colors[pair[0]] = new Color(pair[1]);
                else
                    colors[pair[0]].pairs.Add(pair[1]);

                if (colors[pair[1]] == null)
                    colors[pair[1]] = new Color(pair[0]);
                else
                    colors[pair[1]].pairs.Add(pair[0]);
            }

            Tree t = new Tree();
            t.root = new Node(0);
            PopulateTree(t.root);

            long ans = t.CountMatchingLeaves(t.root, totalTiles - 1) % 1000000007;
            Console.WriteLine(ans);

            s.Stop();
            Console.WriteLine(s.ElapsedMilliseconds);
        }

        static void PopulateTree(Node root)
        {
            for (int i = root.tile + 1; i < totalTiles; i++)
            {
                if (colors[tileColors[i]] == null) continue;
                if (colors[tileColors[i]].Compatible(tileColors[root.tile]))
                {
                    var node = new Node(i);
                    root.children.Add(node);
                    PopulateTree(node);
                }
            }
        }
    }

    class Color
    {
        public List<int> pairs = new List<int>();

        public Color(int pair)
        {
            pairs.Add(pair);
        }

        public bool Compatible(int c)
        {
            return pairs.Contains(c);
        }
    }

    class Node
    {
        public List<Node> children = new List<Node>();
        public int tile;

        public Node(int tile)
        {
            this.tile = tile;
        }
    }

    class Tree
    {
        public Node root;

        public List<Node> GetMatchingLeaves(Node root, int match)
        {
            if (root.children.Count == 0)
            {
                if (root.tile == match)
                {
                    return new List<Node>() { root };
                }
                return new List<Node>();
            }

            List<Node> list = new List<Node>();
            foreach(var c in root.children)
            {
                list.AddRange(GetMatchingLeaves(c, match));
            }
            return list;
        }

        public long CountMatchingLeaves(Node root, int match)
        {
            if (root.children.Count == 0)
            {
                if (root.tile == match)
                {
                    return 1;
                }
                return 0;
            }

            long count = 0;
            foreach (var c in root.children)
            {
                count += CountMatchingLeaves(c, match);
            }
            return count;
        }
    }

Answer 1

Вы всегда можете переписать рекурсию как итерацию, обычно используя класс стека, а не полагаясь на стек вашего потока. Для вашего кода это будет выглядеть так:

static void PopulateTree(Node start)
{
    var nodes = new Stack<Node>();
    nodes.Push(start);

    while(nodes.Count != 0)
    {
        var root = nodes.Pop();

        for (int i = root.tile + 1; i < totalTiles; i++)
        {
            if (colors[tileColors[i]] == null) continue;
            if (colors[tileColors[i]].Compatible(tileColors[root.tile]))
            {
                var node = new Node(i);
                root.children.Add(node);
                nodes.Push(node);
            }
        }
    }
}

Проверка while l oop дополнительных элементов эквивалентна вашему завершающему условию в рекурсии.