本地递归函数中的yield return

Question

我认为使用新的C#本地函数可以摆脱强制性的私有递归函数。显然，此函数“应该”对树进行一些后序遍历。所以，只有在没有左右子节点可用时才给出元素。

代码编译，它“工作”，但是当调试时忽略了对本地函数的递归调用：PostOrderRecursive(currentNode.Left)和PostOrderRecursive(currentNode.Right)，因此完全没有进行递归操作。

问题出在哪里？谢谢！

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;
    }
}

- Christoph

---

HasLeft 或 HasRight 是否有一个为 true？如果没有，调试它们并找出原因。 - fredrik

Answer 1

嵌套方法在使用 yield return 时与常规方法的行为没有任何不同。

问题并非在于忽略了这些方法，而是您没有使用它们返回的值，这使它们变得毫无意义。实际上，您甚至不会递归地进入方法体，因为这只有在对由返回的 IEnumerable<> 调用 GetEnumerator() 并调用 MoveNext() 枚举器后才会发生。

不幸的是，C# 没有一种 "yield foreach" 的语法，所以您必须遍历所有的值并直接使用 yield 进行返回:

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;
    }
}

需要注意的一点是：该实现性能较差，因为它需要创建许多迭代器。一种避免递归但保持节点进程的堆栈或队列的实现可能更加高效。如果您有任何大型树，请牢记这一点，但如果性能不是问题，保持简单可能是有意义的。

- Jon Skeet

---

F# 的 yield! 正好解决了这个问题，现在是使用它的完美时机。 - Richard

我明白了。谢谢！我会尽快接受答案。 - Christoph

@Richard：是的，我也想看到这样的东西。C#团队已经注意到了这个问题，但我不知道是否会有任何进展：https://github.com/dotnet/csharplang/issues/378 - Jon Skeet

@Christoph 看起来 Roslyn 有一个更新的问题：https://github.com/dotnet/roslyn/issues/25052 - Richard

你可以使用以下代码：return PostOrderRecursive(currentNode.Left).Concat(PostOrderRecursive(currentNode.Right)).Append(currentNode.element); - Joel Coehoorn

Answer 2

我刚刚从另一个问题中偶然发现了这个。它现在非常老，但看起来很有趣，我想添加另一种方法来完成这个，更接近原始代码：

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

    IEnumerable<ElementType> PostOrderRecursive(BinaryTree<ElementType> currentNode)
    {
        IEnumerable<ElementType> result = Enumerable.Empty<ElementType>();
        if (currentNode.HasLeft)
            result = result.Concat(PostOrderRecursive(currentNode.Left));
        if (currentNode.HasRight)
            result = result.Concat(PostOrderRecursive(currentNode.Right));

        return result.Append(currentNode.element);
    }
}

- Joel Coehoorn