title: NonRecursive Equivalent of Lazy Recursive Functions
body: <p>Consider the following code implementing a depth first search on a Rose Tree:</p>
  
  <pre><code>public class RoseTree&lt;T&gt;
  {
      public T Value;
      public IEnumerable&lt;Lazy&lt;RoseTree&lt;T&gt;&gt; Children;
  
      public IEnumerable&lt;T&gt; Flatten()
      {
          yield return Value;
          foreach (var childValue in Children.SelectMany(t =&gt; t.Value.Flatten()))
              yield return childValue;
      }
  }
  </code></pre>
  
  <p>I was struggling to come up with an equivalent non-recursive equivalent. In particular, though a strict non-recursive, quasi-equivalent function is easy to come by, e.g:</p>
  
  <pre><code>public IEnumerable&lt;T&gt; FlattenIteratively()
  {
      var roseTreeQueue = new Stack&lt;RoseTree&lt;T&gt;&gt;();
      var values = new Queue&lt;T&gt;();
      roseTreeQueue.Push(this);
  
      while (roseTreeQueue.Any())
      {
          var top = roseTreeQueue.Pop();
          values.Enqueue(top.Value);
  
          foreach (var child in top.Children.Reverse())
              roseTreeQueue.Push(child.Value);
      }
  
      return values;
  } 
  </code></pre>
  
  <p>While this yields the same result as <code>Flatten</code> for finite trees with defined values, it fails for infinite trees or for trees with undefined values. Does anyone see a way of writing a non-recursive method for traversing this structure with the same characteristics as the recursive method.</p>
  
  <p>Note: given C#'s rewriting of <code>yield return</code> functions, calling the first method <code>recursive</code> is somewhat misleading. If anyone has a more precise term, I'd be happy to have it.</p>