在 C# 中防止“进程因 StackOverflowException 而终止”

Question

我有一个程序可以根据输入数据构建一个非常大的树并通过递归遍历它。我已经在较小的输入（因此较小的树）上测试了该程序，并且它按预期运行。然而，当输入数据大得多时，我运行变为 'Process is terminated due to WhosebugException'。我假设这是由于堆栈运行ning out of space。有什么办法可以防止这种情况发生，还是我必须改为通过迭代来构建树？或者我可能在某处遗漏了无限递归的情况？

代码如下：

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

您始终可以将递归重写为迭代，通常是使用堆栈 class 而不是依赖线程的堆栈。对于您的代码，它看起来像这样：

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 循环检查更多项目等同于递归中的终止条件。

在 C# 中防止“进程因 StackOverflowException 而终止”

Prevent ' Process is terminated due to StackOverflowException' in C#

c#

stack-overflow

tree

recursion