一个正确实现的递归延迟迭代器函数会不会出现堆栈溢出吗？

Question

tl;dr;

在C#中，你能保证一个懒惰的迭代器函数只调用它自己，并且有一个有效的递归退出条件不会导致堆栈溢出吗？

详细问题：

我知道通常你不能保证C#编译器(或JIT)生成的尾部调用优化(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方法。

然后，main方法再次调用MoveNext。第一个迭代器向第二个迭代器请求它的第二项，第二个迭代器到达它的foreach方法，创建第三个迭代器，并从中获得一个值。该值一直向上传递。

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

当运行代码时，我们可以看到事情完全按照这里所描述的那样工作，堆栈将溢出。

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

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

所以在这一点上，我们有两个问题要解决。首先，如果我们认识到我们处于这种情况下，我们实际上可以避免创建额外的状态机，从而避免不断增加的堆栈空间。这不会那么容易，可能不像传统的非迭代器块TCO那么容易。您需要将状态机的所有实例字段设置为在调用Foo时创建的状态机的任何实例字段。在这一点上，我只想挥动我的手，说这听起来是可能的，但并不完全是超级的。

然后我们就有了另一个问题。我们如何才能认识到我们实际上处于TCO有效的位置？我们需要递归地调用我们自己，我们不需要对方法调用做任何事情，只需要迭代整个东西并按原样产生每一项，我们不需要在try或using块中(否则finally块将会丢失)，并且在迭代之后不能有任何方法。

现在，如果有一个yield foreach运算符，这就不会那么糟糕了。您已经建立了这样一条规则:如果迭代器块中的最后一条语句是一个yield foreach运算符，并在最后递归调用该方法，则应用TCO。遗憾的是，在C#中(与其他.NET语言不同)，我们没有yield foreach运算符。我们需要键入整个foreach运算符，同时除了按原样生成项目之外，什么也不做。这看起来...有点尴尬。

重述一下：

• 编译器是否有可能对递归迭代器块使用尾部调用优化？

​

• 是由编译器完成的吗？
  • 它看起来不是这样。

​

将此支持添加到编译器中是否特别可行? not.可能是

• ？

​