正确实现的递归惰性迭代器函数永远不会堆叠溢出吗?

本文关键字：溢出永远函数实现递归迭代器 | 更新日期: 2023-09-27 18:18:15

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它只是一个堆计算，似乎在调用迭代它时，它可以知道它是一个堆计算(它是函数的一部分，它是一个迭代器函数(，因此立即跳出它的当前帧并将堆计算扩展到一个新帧 - 在递归调用之前没有额外的堆栈空间企图。。。

这种直觉可能完全没有根据...

正确实现的递归惰性迭代器函数永远不会堆叠溢出吗?

因此，让我们以一个示例方法打开，以便我们有一些可以参考的内容：

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 时将创建的状态机的任何实例字段。 在这一点上，我只想挥挥手，说这听起来是可能的，但并不完全是超级的。

然后我们还有另一个问题。我们如何认识到我们实际上处于TCO有效的位置？我们需要递归地调用自己，除了迭代整个事情并完全按照原样生成每个项目之外，我们不需要对该方法调用执行任何操作，我们不需要处于try或using块中(否则finally块将丢失(，并且迭代后不能有任何方法。

现在，如果有一个yield foreach运算符，那么情况就不会那么糟糕。您只需要设置一个规则，如果迭代器块中的最后一个语句是yield foreach运算符，并在最后递归调用该方法，则应用 TCO。遗憾的是，在 C# 中(与其他一些 .NET 语言不同(，我们没有yield foreach运算符。我们需要键入整个foreach运算符，同时除了完全按原样生成项目之外，无需执行任何其他操作。那似乎...有点尴尬。

回顾一下：

编译器是否可以对递归迭代器块使用尾部调用优化？
- 最有可能。
编译器曾经做过吗？
- 似乎并非如此。
支持添加到编译器中是否特别可行？
- 应该不会。

相关文章：

最新信息: