Defensive Code to prevent Infinite Recursion in Parent/Child Hierarchy

Question

Given an Object as Such

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();
    }   
}

and if used (abused!?) in such a way

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());     
}

how does one be defensive about this kind of scenario.

This code as it stands produces a stackoverflow, infinite recursion, or memory exceeded error.

In a (IIS) website this was causing the w3 worker processes to crash, and eventually the app pool to shut down (Rapid-Fail Protection)

The code above is indicative only to reproduce the problem. In the actual scenario, the structure is coming from a database with Id and ParentId.

Database table structure similar to

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

The issue is that the creation of the 'things' by users is not preventing a incestuous relationship (i.e. a Parent could have children (who could have children etc.... that one eventually points at the parent again). One could put a constraint on the db to prevent the thing not being its own parent (makes sense), but depending on depth this could get ugly, and there is some argument that a circular reference may be required (we are still debating this....)

So arguably the structures can be circular, but if you want to render this kind of structure on a web page say as a <ul><li><a> tag kind of thing in a parent/child menu, how does one become proactive about dealing with this user generated data issue in code?

.NET fiddle here

Answer 1

One way would be to include a collection of visited nodes in the recursive call. If visited before you are in a cycle.

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();
}