Recursive method turning flat structure to recursive
Below is the code for my approach.  A benefit is that the heirarchy goes both ways; up and down.  While the parent object contains a list of child objects, each child has a reference to the parent object.

Some differences from your original setup:


The ParentId property on FlatObject is nullable, so objects that have no parent will have null.
The Children property on RecursiveObject is IEnumerable instead of List.  This prevents consumers from modifying the contents of the list.  If you want to allow consumers to add/remove items from the list, then RecursiveObject should expose methods to perform those actions so that you can make sure that the Parent property is properly assigned when a child is added/removed.
I've made the Id, Parent, and Children properties on RecursiveObject read-only.  This certainly isn't necessary, but you can do that if desired.  This is the reason why I made the FlatObjectsToRecursiveObjects method as a static method of the RecursiveObjects class; so that it can have access to the private property setters.


The gist of this approach is that we first convert the FlatObjects to RecursiveObjects and store them in a dictionary keyed by the Id.  Then, we do another pass over the FlatObjects in order to assign the Parent and Children properties of each RecursiveObject, using the dictionary to perform the necessary look-ups with the FlatObject's Id and ParentId properties.

class FlatObject
{
    public int Id { get; set; }
    public int? ParentId { get; set; }
}

class RecursiveObject
{
    public int Id { get; private set; }
    public RecursiveObject Parent { get; private set; }
    public IEnumerable&lt;RecursiveObject&gt; Children { get; private set; }

    public static IEnumerable&lt;RecursiveObject&gt; FlatObjectsToRecursiveObjects(IEnumerable&lt;FlatObject&gt; flatObjects)
    {
        // convert flat objects into heirarchial objects and store them in a dictionary keyed with the object's Id
        var recursiveObjectsById = flatObjects.Select(item =&gt; new RecursiveObject { Id = item.Id }).ToDictionary(item =&gt; item.Id);

        // group flat objects by their ParentId
        var flatObjectsGroupedByParentId = flatObjects.Where(item =&gt; item.ParentId.HasValue).GroupBy(item =&gt; item.ParentId.Value);
        foreach (var group in flatObjectsGroupedByParentId)
        {
            // find each group's parent object
            RecursiveObject parent;
            if (recursiveObjectsById.TryGetValue(group.Key, out parent))
            {
                // convert the group of flat objects to a list of heirarchial objects by looking up the correct heirarchial object from the dictionary
                parent.Children = group.Select(item =&gt; recursiveObjectsById[item.Id]).ToList();

                // assign the parent object to each child object
                foreach (var child in parent.Children)
                {
                    child.Parent = parent;
                }
            }
            else
            {
                // something's wrong!!!  ParentId refers to a non-existant object.
            }
        }

        return recursiveObjectsById.Values;
    }
}


EDIT:  Added an "improved" version of my original approach, shown below.  The following implementation provides the following benefits:


The Children property on RecursiveObject never returns a null, but it still retains the "benefit" of lazy initialization.  The Children property getter checks if the _Children field is null, and if so it returns the default instance of the EmptyEnumerable&lt;RecursiveObject&gt; class (code included).
Children can now be added/removed using the new AddChild, RemoveChild, and AddChildren methods on RecursiveObject.
The FlatObjectsToRecursiveObjects method is slightly simpler now because it utilizes the new AddChildren method.
The FlatObjectsToRecursiveObjects method no longer has to be a member of the RecursiveObject class, since it does not access any private details of the class.
My setup code includes a second root (new FlatObject(9,-1)) and circular references (new FlatObject(10,10) and new FlatObject(0,2)), just to verify that the implementation can handle these special cases.

class FlatObject
{
    public int Id { get; set; }
    public int? ParentId { get; set; }

    public FlatObject(int id)
    {
        this.Id = id;
    }

    public FlatObject(int id, int parentId)
        : this(id)
    {
        this.ParentId = parentId;
    }
}

class RecursiveObject
{
    public int Id { get; private set; }
    public RecursiveObject Parent { get; private set; }
    private List&lt;RecursiveObject&gt; _Children;

    public IEnumerable&lt;RecursiveObject&gt; Children
    {
        get
        {
            IEnumerable&lt;RecursiveObject&gt; value = _Children;
            if (value == null)
                value = EmptyEnumerable&lt;RecursiveObject&gt;.Default;
            return value;
        }
    }

    public RecursiveObject(int id)
    {
        this.Id = id;
    }

    public void AddChild(RecursiveObject child)
    {
        if (_Children == null)
            _Children = new List&lt;RecursiveObject&gt;();
        _Children.Add(child);
        child.Parent = this;
    }

    public bool RemoveChild(RecursiveObject child)
    {
        if (_Children != null)
        {
            bool removed = _Children.Remove(child);
            if (removed)
                child.Parent = null;
            return removed;
        }
        else
        {
            return false;
        }
    }

    public void AddChildren(IEnumerable&lt;RecursiveObject&gt; children)
    {
        if (children == null)
            throw new ArgumentNullException("children");

        if (_Children == null)
            _Children = new List&lt;RecursiveObject&gt;(children);
        else
            _Children.AddRange(children);

        foreach (var child in children)
        {
            child.Parent = this;
        }
    }
}

class Program
{
    public static IEnumerable&lt;RecursiveObject&gt; FlatObjectsToRecursiveObjects(IEnumerable&lt;FlatObject&gt; flatObjects)
    {
        // convert flat objects into heirarchial objects and store them in a dictionary keyed with the object's Id
        var recursiveObjectsById = flatObjects.Select(item =&gt; new RecursiveObject(item.Id)).ToDictionary(item =&gt; item.Id);

        // group flat objects by their ParentId
        var flatObjectsGroupedByParentId = flatObjects.Where(item =&gt; item.ParentId.HasValue).GroupBy(item =&gt; item.ParentId.Value);
        foreach (var group in flatObjectsGroupedByParentId)
        {
            // find each group's parent object
            RecursiveObject parent;
            if (recursiveObjectsById.TryGetValue(group.Key, out parent))
            {
                // convert the group of flat objects to a list of heirarchial objects by looking up the correct heirarchial object from the dictionary
                parent.AddChildren(group.Select(item =&gt; recursiveObjectsById[item.Id]));
            }
            else
            {
                // something's wrong!!!  ParentId refers to a non-existant object.
            }
        }

        return recursiveObjectsById.Values;
    }

    static void Main(string[] args)
    {
        List&lt;FlatObject&gt; flatObjects = new List&lt;FlatObject&gt;()
            {
                new FlatObject(1,0),
                new FlatObject(2,0),
                new FlatObject(3,0),
                new FlatObject(4,0),
                new FlatObject(5,1),
                new FlatObject(6,2),
                new FlatObject(7,6),
                new FlatObject(8,6),
                new FlatObject(9,-1),
                new FlatObject(10,10),
                new FlatObject(0,2),
            };

        var recursiveObjects = FlatObjectsToRecursiveObjects(flatObjects).ToList();
    }
}

#region Universal Code

class EmptyEnumerator&lt;T&gt; : IEnumerator&lt;T&gt;
{
    public static readonly EmptyEnumerator&lt;T&gt; Default = new EmptyEnumerator&lt;T&gt;();

    public T Current
    {
        get { throw new InvalidOperationException(); }
    }

    public void Dispose()
    {
    }

    object System.Collections.IEnumerator.Current
    {
        get { throw new InvalidOperationException(); }
    }

    public bool MoveNext()
    {
        return false;
    }

    public void Reset()
    {
    }
}

class EmptyEnumerable&lt;T&gt; : IEnumerable&lt;T&gt;
{
    public static readonly EmptyEnumerable&lt;T&gt; Default = new EmptyEnumerable&lt;T&gt;();

    public IEnumerator&lt;T&gt; GetEnumerator()
    {
        return EmptyEnumerator&lt;T&gt;.Default;
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }
}

#endregion