Recursion in C# iterator

Question

Is it possible to use recursion in an iterator implementing System.Collections.IEnumerable? I have a tree structure declared roughly like this:

public class Node
{
    public Node Sibling;
    public Node Child;
}

I would like to iterate over the nodes in a tree. I would like to do something like this (pseudocode, I guess this won't compile):

public class NodeIterator : System.Collections.IEnumerable
{
    Node m_root;

    public System.Collections.IEnumerator GetEnumerator()
    {
        recursiveYield(m_root);
    }

    System.Collections.IEnumeraton recursiveYield(Node node)
    {
        yield return node;
        if (node.Child)
        {
            recursiveYield(node.Child);
        }
        if (node.Sibling)
        {
            recursiveYield(node.Sibling);
        }
    }
}

Is this somehow possible? I realise this can be solved without recursion using a Node deque in the GetEnumerator function.

Should work. Did you try this out ? the clients should not care how it is implemented - it just has to be able to iterate through the receiver. If recursion makes your code simpler, use it. — Gishu, Nov 17 '10 at 06:40
@Gishu - should work (aside from `IEnumeraton`), but it ignores the return value of `recursiveYield(node.Child)` and `recursiveYield(node.Sibling)`. — Kobi, Nov 17 '10 at 06:42
Not exactly a duplicate, but [C# Performance of nested yield in a tree](http://stackoverflow.com/questions/1043050/c-performance-of-nested-yield-in-a-tree) shows some solutions and discusses some performance implications. — Albin Sunnanbo, Nov 17 '10 at 07:08

John Leidegren · Accepted Answer · 2010-11-17T06:47:53.503

21

Yes, all you need is to iterate the return value from the call site. Like so:

IEnumerable<T> Recursive(Node node)
{
    yield return node;
    foreach (var siblingNode in Recursive(node.Sibling))
    {
        yield return siblingNode;
    }
    foreach (var childNode in Recursive(node.Child))
    {
        yield return childNode;
    }
}

For the record, this isn't better than using a queue to achieve e.g. breadth-first traversal. The memory requirement for something like this is identical in the worst case.

edited Nov 17 '10 at 06:47

answered Nov 17 '10 at 06:39

John Leidegren

59,920
20
131
152

Do I need to create an iterator at all or would it be possible to create a static function which recursively yields the different values: `static IEnumberable Recursive(Node node)` and then at client `foreach(var node in Recursive(root))`? – Andreas Brinck Nov 17 '10 at 06:48
Hi John Leidegren, yes this is pretty beautiful - short & sweet:) But are you sure the memory requirement will be identical ? If I remember correctly checking similar code it was not at all! New ArrayList or List create on every call. – ivo s Nov 17 '10 at 07:13
@Andreas Brinck The contextual keyword `yield` is used to tell the compiler that the return value of this method is a sequence of values `IEnumerable` rather than a single value. That's why and how this works. If you implement the traversal yourself, you'll end up three times as much code. If you're asking if you don't need to implement of IEnumerable/IEnumerator yourself then that's true. This can be a static method that can be used by the client as suggested. – John Leidegren Nov 17 '10 at 07:17
may I add that in F# you can do this more naturally using the yield! operator (spares you from iterating over the result of the recursive invocation). – Johannes Rudolph Nov 17 '10 at 07:30
I need to bring myself to write more code in F# functional was never a dull moment. – John Leidegren Nov 17 '10 at 17:00
One thing to point out is that this approach will allocate a new Enumerator for each element in the tree. Each of these iterators needs to keep track of their state in enumerating the tree underneath it. It's effectively turning a tree of elements into a tree of enumerators. The code is certainly small and compact, but I suspect the memory/GC impact and general performance may not be particularly good. – Niall Connaughton Jan 26 '17 at 01:01
@NiallConnaughton yes, this is an excellent point. Something discussed in Eric Lippert's old blog extensively. Couldn't fint he post though but I did find this http://codereview.stackexchange.com/a/5661/10239 – John Leidegren Jan 26 '17 at 05:30

score 3 · Answer 2 · edited Nov 03 '13 at 09:05

3

No because the recursiveYield(Node node) function would return a collection and you can only yield an item

edited Nov 03 '13 at 09:05

zero323

322,348
103
959
935

answered Nov 17 '10 at 06:44

ivo s

144
3

While it is true (and unfortunate) you cannot combine `return collection` with `yield return item`, there's an easy workaround. – Kobi Nov 17 '10 at 06:46
Well, you should generally prefer the working workarounds `:)` – Kobi Nov 17 '10 at 06:50
That is what I usually use at work but I hope tomorrow will be the day I do it right:) Every day I hope ... maybe tomorrow:) – ivo s Nov 17 '10 at 06:51
Now @John Leidegren code works & I've written similar but performance is not better! You create an List or ArrayList (if I'm not mistaken, don't have disassembler) on every call! But you are ready interested in one item. This should never see deployment! I changed similar code when I looked at the IL. While it's short * beautiful it's not the right way for this problem. – ivo s Nov 17 '10 at 07:09
@ivo s, it does not really return a collection. It returns an Enumerator. The difference is that a collection contains it values, but the Enumerator produces the values on the fly. The Enumerator can only be enumerated once (without creating a new Enumerator), while a collection allows repeated enumerations and might allow access by index or key. – Albin Sunnanbo Nov 17 '10 at 08:44
@ Albin Sunnanbo Actually the enumeration never takes place until runtime but when it does run how do you think this function returns values ? Unless the JIT compiler is smart enough to realize that there is no code pass the yield statement (which I doubt) and merges the calls in one?! it would have to store the pointers somewhere on heap/stack(<-not important) right ? BTW when you say 'Enumerator' isn't that some kind of a data structure which (will eventually or at the mean time) contains nodes ??:) – ivo s Nov 17 '10 at 08:57

Recursion in C# iterator

2 Answers2