c# - 正确实现的递归惰性迭代器函数将不会堆栈溢出吗？

Question

tl; dr;

在C#中，您是否可以确保仅调用自身且确实具有有效的递归退出条件的惰性迭代器函数不会导致堆栈溢出？

详细问题:

我知道，通常来讲，您无法保证由C#编译器(或JIT)生成的尾部调用优化(TCO)指令，因此尽管您可能会获得TCO，但不能保证。

鉴于对TCO的这种认可，我想知道是否由于懒惰的迭代器函数(使用yield return等)作为协程的性质-每个尾部调用是否甚至占用堆栈空间？由于协程的重新进入，我的直觉是默认情况下优化了每个尾部调用，因为从父级框架跳出函数并跳入下一个而不是创建新框架的能力似乎很自然。

是C#中的这种行为，还是C#迭代器函数的递归调用从当前框架创建了一个新框架，而不是弹出到父框架并使用新参数重新输入？

例子:

public static IEnumerable<IEnumerable<T>> GeneratePermutations<T>(this IEnumerable<T> choices, int numberToChoose)
{
    if (numberToChoose == 1)
    {
        foreach (var choice in choices)
            yield return new T[] { choice };
        yield break;
    }

    var subPermutations = choices.SelectMany(choice =>
        choices.Where(elem => !EqualityComparer<T>.Default.Equals(elem, choice))
            .GeneratePermutations(numberToChoose - 1)
            .Select(permutation => (new T[] { choice }).Concat(permutation)));
    foreach (var perm in subPermutations)
        yield return perm;
}

我的直觉基于上面的示例 subPermutations只是一个堆计算，似乎在调用时对其进行了迭代，它可以知道它是堆计算(它是函数sig的一部分，它是一个迭代器函数)，因此立即从当前帧跳出并将扩展的计算扩展到新的帧-尝试递归调用之前的空间不会花费额外的堆栈空间...

这种直觉可能是完全没有根据的。

Answer 1

因此，让我们以示例方法开始，以便我们可以引用:

public static IEnumerable<int> Foo()
{
    yield return 1;
    foreach (var n in Foo())
        yield return n;
}

这是我们的递归迭代器块。我只想花一点时间来指出此方法的一些属性，这些属性可能(或可能不)最终变得有意义。

有一个递归调用，但是递归调用在yield之后。

当我们到达递归调用时，那之后我们唯一要做的就是产生所有结果。每个项目都没有投影，没有finally块，在这些产量之后也没有任何东西，等等。

那么，当一些代码去写以下内容时会发生什么呢？

foreach(var n in Foo())
    Console.WriteLine(n);

好吧，当我们到达此语句时，第一件事就是将 Foo()评估为一个值。在这种情况下，这将创建代表序列生成器的状态机。我们实际上并没有执行方法主体中的任何代码。

接下来，我们称为 MoveNext。我们打了第一个 yield块，产生一个值，然后打印出来。

之后，最外层再次调用 MoveNext。在这里，我们的状态机的 MoveNext方法到达了它自己的 foreach块。它将像 Main方法一样，将 Foo()评估为一个值，从而创建第二个状态机。然后它将立即在该状态机上调用 MoveNext。第二个状态机将到达它的第一个 yield，它将向第一个迭代器产生该值，这将把它返回到主方法，该主方法将打印它。

然后main方法再次调用 MoveNext。第一个迭代器向第二个迭代器询问第二个迭代器，第二个迭代器到达其 foreach方法，创建第三个迭代器，并从中获取一个值。该值将一直传递。

正如我们每次在这里看到的那样，当我们作为另一个项目的顶级迭代器时，堆栈总是比以前深一层。尽管事实上我们正在使用状态机，并且创建迭代器并不会消耗大量的堆栈空间，但是获取序列中的下一项将消耗越来越多的堆栈空间，直到耗尽为止。

运行代码时，我们可以看到事情完全按照此处的描述进行，并且堆栈将溢出。

那么，如何对其进行优化？

好吧，我们希望在这里做的是让顶级迭代器意识到，当到达 foreach时，“从现在开始，我序列中的其余项目与递归调用中的所有项目相同”。这听起来很像典型的TCO情况。

因此，目前我们要解决两个问题。首先，如果我们意识到自己处在这种情况下，是否可以避免创建其他状态机，从而避免堆栈空间的不断增加。这不是那么容易，可能不像传统的非迭代器TCO那样容易。您需要将状态机的所有实例字段设置为将调用 Foo所创建的状态机的实例字段。在这一点上，我只是挥挥手，说这听起来可能，但并不是每一个都 super 好。

然后我们还有另一个问题。我们如何才能知道我们实际上处于TCO有效的位置？我们需要递归地调用自己，除了迭代整个过程并按原样生成每个项目外，我们不需要对该方法调用做任何事情，我们不必位于 try或 using块中(否则 finally块会丢失)，并且该迭代之后没有任何方法。

现在，如果有一个 yield foreach运算符，那还不错。您只需设置以下规则:如果iterator块中的最后一条语句是 yield foreach运算符，并且最后对该方法进行了递归调用，则应用TCO。遗憾的是，在C#中(与其他.NET语言不同)，我们没有 yield foreach运算符。我们需要输入整个 foreach运算符，同时除了完全按原样产生项目外，不执行其他任何操作。看来...有点尴尬。

回顾一下:

编译器是否可以将Tail Call Optimization用于递归迭代器块？

最有可能。

是否由编译器完成？

看来并非如此。

将这种支持添加到编译器中是否特别可行？

可能不会。