c# - 防止父/子层次结构中无限递归的防御代码

Question

给定一个对象

public class Thing
{  
    public Thing() { this.children = new List<Thing>();}

    public int Id {get; set;}       
    public string Name {get; set;}      
    public List<Thing> children{ get; set;}

    public string ToString(int level = 0)
    {
        //Level is added purely to add a visual hierarchy
        var sb = new StringBuilder();
        sb.Append(new String('-',level));
        sb.AppendLine($"id:{Id} Name:{Name}");          
        foreach(var child in children)
        {
                sb.Append(child.ToString(level + 1));
        }       
        return sb.ToString();
    }   
}

如果以这种方式使用(滥用!？)

public static void Main()
{
    var root = new Thing{Id = 1,Name = "Thing1"};       
    var thing2 = new Thing{Id = 2,Name = "Thing2"};             
    var thing3 = new Thing{Id = 3,Name = "Thing3"};     
    root.children.Add(thing2);
    thing2.children.Add(thing3);                         
    thing3.children.Add(root);  //problem is here       
    Console.WriteLine(root.ToString());     
}

对于这种情况，人们如何防御。

这段代码会产生stackoverflow、无限递归或内存超出错误。

在 (IIS) 网站中，这导致 w3 工作进程崩溃，并最终关闭应用程序池(快速失败保护)

上面的代码仅用于重现问题。在实际场景中，该结构来自具有 Id 和 ParentId 的数据库。

数据库表结构类似

CREATE TABLE Thing(
    Id INT NOT NULL PRIMARY KEY,
    Name NVARCHAR(255) NOT NULL,
    ParentThingId INT NULL //References self
)

问题是用户创建的“事物”并不能阻止乱伦关系(即 parent 可以有 child (谁可以有 child 等......最终再次指向 parent )。一个可以对数据库施加约束以防止事物不是它自己的父对象(有道理)，但是根据深度，这可能会变得丑陋，并且有一些论点认为可能需要循环引用(我们仍在争论这个...... ..)

所以可以说结构可以是圆形的，但是如果你想在网页上呈现这种结构，可以说是 <ul><li><a>在父/子菜单中标记某种东西，如何在代码中主动处理这个用户生成的数据问题？

.NET fiddle here

Answer 1

一种方法是在递归调用中包含一组已访问节点。如果在您进入循环之前访问过。

public string ToString(int level = 0, HashSet<int> visited)
{
        foreach(var child in children)
        {
                if(visited.Add(child.Id))
                   sb.Append(child.ToString(level + 1, visited));
                else
                   //Handle the case when a cycle is detected.
        }       
        return sb.ToString();
}