Yield return in local recursive function

Question

I thought with the new fancy C# local functions I could get rid of the mandatory private recursion function. Obviously this function "should" do some post order traverasal of a tree. So, only give the element IFF there is no left or right child available.

The code compiles, it "works", but the recursive calls to the local function: PostOrderRecursive(currentNode.Left); and PostOrderRecursive(currentNode.Right); are ignored when debugging. So no recursion is performed at all.

What is the problem here? Thanks in advance!

public IEnumerable<ElementType> GetSubtreeFlattenedPostOrder()
{
    return PostOrderRecursive(this);

    IEnumerable<ElementType> PostOrderRecursive(BinaryTree<ElementType> currentNode)
    {
        if (currentNode.HasLeft)
            PostOrderRecursive(currentNode.Left);
        if (currentNode.HasRight)
            PostOrderRecursive(currentNode.Right);

        yield return currentNode.element;
    }
}

Answer 1

Nested methods don't behave any differently to regular methods with respect to the effect of yield return.

It's not that the methods are ignored - it's that you're not using the value returned from them, which makes them pointless. In fact, you won't even enter the body of the method recursively, because that doesn't happen until you call MoveNext() on the enumerator returned by the GetEnumerator() call to the returned IEnumerable<>.

Unfortunately C# doesn't have a sort of "yield foreach" syntax, so you have to iterate over all the values and yield them directly:

public IEnumerable<ElementType> GetSubtreeFlattenedPostOrder()
{
    return PostOrderRecursive(this);

    IEnumerable<ElementType> PostOrderRecursive(BinaryTree<ElementType> currentNode)
    {
        if (currentNode.HasLeft)
        {
            foreach (var node in PostOrderRecursive(currentNode.Left))
            {
                yield return node;
            }
        }
        if (currentNode.HasRight)
        {
            foreach (var node in PostOrderRecursive(currentNode.Right))
            {
                yield return node;
            }
        }

        yield return currentNode.element;
    }
}

One point to note: this implementation performs poorly, because it needs to create so many iterators. An implementation which avoided recursion but kept a stack or queue of nodes to process could be a lot more efficient. You should bear that in mind if you have any large trees, but it may make sense to keep it simple if performance isn't an issue.