title: Why does using IEnumerable<T> inside a recursive method make it much slower than using a List<T>?
body: <p>I am using a recursive method to go through a tree of items and add its children to a flat collection:</p>
  
  <pre><code>public class Thing
  {
      public int Id { get; set; }
      public string Name { get; set; }
      public int? ParentId { get; set; }
  }
  
  void Main()
  {
      var sampleData = new List&lt;Thing&gt;
      {
          new Thing { Id = 1,  Name = "root1", ParentId = null },
          new Thing { Id = 2,  Name = "2", ParentId = 1 },
          new Thing { Id = 3,  Name = "3", ParentId = 1 },
          new Thing { Id = 4,  Name = "4", ParentId = 2 },
          new Thing { Id = 5,  Name = "5", ParentId = 2 },
          new Thing { Id = 6,  Name = "6", ParentId = 2 },
          new Thing { Id = 7,  Name = "7", ParentId = 6 },
          new Thing { Id = 8,  Name = "8", ParentId = 7 },
          new Thing { Id = 9,  Name = "9", ParentId = 8 },
          new Thing { Id = 10,  Name = "10", ParentId = 9 },
          new Thing { Id = 11,  Name = "11", ParentId = 10 },
          new Thing { Id = 12,  Name = "12", ParentId = 11 },
          new Thing { Id = 13,  Name = "13", ParentId = 12 },
          new Thing { Id = 14,  Name = "14", ParentId = 13 },
          new Thing { Id = 15,  Name = "root15", ParentId = null }
      };
  
      var subThings = new HashSet&lt;Thing&gt;();
      var stopWatch = new Stopwatch();
      stopWatch.Start();
      //AddSubThings(subThings, sampleData, new List&lt;int&gt; { 1 });
      AddSubThingsUsingList(subThings, sampleData, new List&lt;int&gt; { 1 });
      stopWatch.Elapsed.Dump();
      subThings.Dump();
  }
  
  private void AddSubThings(HashSet&lt;Thing&gt; resultThings, IEnumerable&lt;Thing&gt; sourceThings, IEnumerable&lt;int&gt; parentIds)
  {
      if (!sourceThings.Any() || !parentIds.Any())
      {
          return;
      }
      var subThings = sourceThings.Where(st =&gt; st.ParentId.HasValue &amp;&amp; parentIds.Contains(st.ParentId.Value));
      resultThings.UnionWith(subThings);
      AddSubThings(resultThings, sourceThings.Except(subThings), subThings.Select(st =&gt; st.Id));
  }
  
  private void AddSubThingsUsingList(HashSet&lt;Thing&gt; resultThings, List&lt;Thing&gt; sourceThings, List&lt;int&gt; parentIds)
  {
      if (!sourceThings.Any() || !parentIds.Any())
      {
          return;
      }
      var subThings = sourceThings.Where(st =&gt; st.ParentId.HasValue &amp;&amp; parentIds.Contains(st.ParentId.Value));
      resultThings.UnionWith(subThings);
      AddSubThingsUsingList(resultThings, sourceThings.Except(subThings).ToList(), subThings.Select(st =&gt; st.Id).ToList());
  }
  </code></pre>
  
  <p>When I use the <code>AddSubThings</code> method it takes around 90 seconds to process. However if I use the <code>AddSubThingsUsingList</code> method it does not even take a second. Why is this?</p>