blocks|key|152574|text|因此，让我们从一个示例方法开始，这样我们就有了一些可以参考的东西：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|152575|public+static+IEnumerable<int>+Foo()
{
++++yield+return+1;
++++foreach+(var+n+in+Foo())
++++++++yield+return+n;
}|code-block|syntax|javascript|152576|这是我们的递归迭代器代码块。我只想花一点时间来调用这个方法的一些属性，这些属性可能(也可能不)最终是相关的。|152577|152578|有一个递归调用，但递归调用是在yield之后。|unordered-list-item|offset|length|style|CODE|152579|当我们到达递归调用时，我们在那之后做的唯一一件事就是产生所有的结果。在每个项目上没有投影，没有finally块，在这些产量之后什么都没有，等等。|152580|152581|那么，当一些代码运行并编写以下代码时会发生什么呢？|152582|foreach(var+n+in+Foo())
++++Console.WriteLine(n);|152583|那么，当我们到达这条语句时，第一件事就是计算Foo()的值。在这种情况下，这将创建表示序列生成器的状态机。不过，我们实际上并没有执行方法体中的任何代码。|152584|接下来，我们调用MoveNext。我们点击第一个yield块，产生一个值，并将其打印出来。|152585|之后，最外层再次调用MoveNext。在这里，状态机的MoveNext方法到达它自己的foreach块。它将像Main方法一样，将Foo()求值为一个值，从而创建第二个状态机。然后，它将立即在状态机上调用MoveNext。第二个状态机将到达它的第一个yield，它将向第一个迭代器生成值，该迭代器将该值返回给将打印它的main方法。|152586|然后，main方法再次调用MoveNext。第一个迭代器向第二个迭代器请求它的第二项，第二个迭代器到达它的foreach方法，创建第三个迭代器，并从中获得一个值。该值一直向上传递。|152587|正如我们在这里看到的，每次我们作为另一项的顶层迭代器时，堆栈总是比以前深一层。尽管我们使用的是状态机，而且创建迭代器不会消耗大量堆栈空间，但获取序列中的下一项将消耗越来越多的堆栈空间，直到耗尽为止。|152588|当运行代码时，我们可以看到事情完全按照这里所描述的那样工作，堆栈将溢出。|152589|那么，如何对其进行优化呢？|152590|好吧，我们希望在这里做的是让顶级迭代器意识到，当它到达foreach时，“从现在开始，我序列中的其余项与递归调用中的所有项都相同”。这听起来确实很像典型的TCO情况。|152591|所以在这一点上，我们有两个问题要解决。首先，如果我们认识到我们处于这种情况下，我们实际上可以避免创建额外的状态机，从而避免不断增加的堆栈空间。这不会那么容易，可能不像传统的非迭代器块TCO那么容易。您需要将状态机的所有实例字段设置为在调用Foo时创建的状态机的任何实例字段。在这一点上，我只想挥动我的手，说这听起来是可能的，但并不完全是超级的。|152592|然后我们就有了另一个问题。我们如何才能认识到我们实际上处于TCO有效的位置？我们需要递归地调用我们自己，我们不需要对方法调用做任何事情，只需要迭代整个东西并按原样产生每一项，我们不需要在try或using块中(否则finally块将会丢失)，并且在迭代之后不能有任何方法。|152593|现在，如果有一个yield+foreach运算符，这就不会那么糟糕了。您已经建立了这样一条规则:如果迭代器块中的最后一条语句是一个yield+foreach运算符，并在最后递归调用该方法，则应用TCO。遗憾的是，在C#中(与其他.NET语言不同)，我们没有yield+foreach运算符。我们需要键入整个foreach运算符，同时除了按原样生成项目之外，什么也不做。这看起来...有点尴尬。|152594|重述一下：|152595|152596|编译器是否有可能对递归迭代器块使用尾部调用优化？|152597|152598|152599|152600|152601|152602|152603|​|152604|152605|是由编译器完成的吗？|152606|它看起来不是这样。|152607|152608|152609|152610|将此支持添加到编译器中是否特别可行?+not.可能是|152611|？|152612|152613|152614|152615|152616|entityMap^0|0|0|0|0|F|5|0|1B|7|0|0|0|0|M|5|0|8|8|O|5|0|A|8|R|8|17|7|1J|4|1T|5|2U|8|3H|5|0|D|8|1H|7|0|0|0|0|R|7|0|3B|3|0|2L|3|2P|5|2Z|7|0|8|D|1T|D|3K|D|49|7|0|0|0|1|1|2|2|1|0|0|0|0|1|1|0|0|0|0|1|1|0|0|0^^$0|@$1|2|3|4|5|6|7|2E|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|2F|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|2G|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|2H|8|@]|9|@]|A|$]]|$1|J|3|K|5|L|7|2I|8|@$M|2J|N|2K|O|P]]|9|@]|A|$]]|$1|Q|3|R|5|L|7|2L|8|@$M|2M|N|2N|O|P]]|9|@]|A|$]]|$1|S|3|-4|5|6|7|2O|8|@]|9|@]|A|$]]|$1|T|3|U|5|6|7|2P|8|@]|9|@]|A|$]]|$1|V|3|W|5|D|7|2Q|8|@]|9|@]|A|$E|F]]|$1|X|3|Y|5|6|7|2R|8|@$M|2S|N|2T|O|P]]|9|@]|A|$]]|$1|Z|3|10|5|6|7|2U|8|@$M|2V|N|2W|O|P]|$M|2X|N|2Y|O|P]]|9|@]|A|$]]|$1|11|3|12|5|6|7|2Z|8|@$M|30|N|31|O|P]|$M|32|N|33|O|P]|$M|34|N|35|O|P]|$M|36|N|37|O|P]|$M|38|N|39|O|P]|$M|3A|N|3B|O|P]|$M|3C|N|3D|O|P]]|9|@]|A|$]]|$1|13|3|14|5|6|7|3E|8|@$M|3F|N|3G|O|P]|$M|3H|N|3I|O|P]]|9|@]|A|$]]|$1|15|3|16|5|6|7|3J|8|@]|9|@]|A|$]]|$1|17|3|18|5|6|7|3K|8|@]|9|@]|A|$]]|$1|19|3|1A|5|6|7|3L|8|@]|9|@]|A|$]]|$1|1B|3|1C|5|6|7|3M|8|@$M|3N|N|3O|O|P]]|9|@]|A|$]]|$1|1D|3|1E|5|6|7|3P|8|@$M|3Q|N|3R|O|P]]|9|@]|A|$]]|$1|1F|3|1G|5|6|7|3S|8|@$M|3T|N|3U|O|P]|$M|3V|N|3W|O|P]|$M|3X|N|3Y|O|P]]|9|@]|A|$]]|$1|1H|3|1I|5|6|7|3Z|8|@$M|40|N|41|O|P]|$M|42|N|43|O|P]|$M|44|N|45|O|P]|$M|46|N|47|O|P]]|9|@]|A|$]]|$1|1J|3|1K|5|6|7|48|8|@]|9|@]|A|$]]|$1|1L|3|-4|5|6|7|49|8|@]|9|@]|A|$]]|$1|1M|3|1N|5|L|7|4A|8|@]|9|@]|A|$]]|$1|1O|3|-4|5|L|7|4B|8|@]|9|@]|A|$]]|$1|1P|3|-4|5|L|7|4C|8|@]|9|@]|A|$]]|$1|1Q|3|-4|5|L|7|4D|8|@]|9|@]|A|$]]|$1|1R|3|-4|5|6|7|4E|8|@]|9|@]|A|$]]|$1|1S|3|-4|5|6|7|4F|8|@]|9|@]|A|$]]|$1|1T|3|-4|5|6|7|4G|8|@]|9|@]|A|$]]|$1|1U|3|1V|5|6|7|4H|8|@]|9|@]|A|$]]|$1|1W|3|-4|5|6|7|4I|8|@]|9|@]|A|$]]|$1|1X|3|1Y|5|L|7|4J|8|@]|9|@]|A|$]]|$1|1Z|3|20|5|L|7|4K|8|@]|9|@]|A|$]]|$1|21|3|-4|5|6|7|4L|8|@]|9|@]|A|$]]|$1|22|3|-4|5|6|7|4M|8|@]|9|@]|A|$]]|$1|23|3|1V|5|6|7|4N|8|@]|9|@]|A|$]]|$1|24|3|25|5|6|7|4O|8|@]|9|@]|A|$]]|$1|26|3|27|5|L|7|4P|8|@]|9|@]|A|$]]|$1|28|3|-4|5|L|7|4Q|8|@]|9|@]|A|$]]|$1|29|3|-4|5|6|7|4R|8|@]|9|@]|A|$]]|$1|2A|3|-4|5|6|7|4S|8|@]|9|@]|A|$]]|$1|2B|3|1V|5|6|7|4T|8|@]|9|@]|A|$]]|$1|2C|3|-4|5|6|7|4U|8|@]|9|@]|A|$]]]|2D|$]]

So, let's open with an example method, so that we have something to reference:

<pre><code>public static IEnumerable&lt;int&gt; Foo()
{
 yield return 1;
 foreach (var n in Foo())
 yield return n;
}
</code></pre>

Here's our recursive iterator block. I just want to take a moment to call out a few properties of this method that may (or may not) end up being relevant. 

<ul>
<li>There is a recursive call, but the recursive call is after a <code>yield</code>. </li>
<li>When we do reach our recursive call, the only thing we do after that point is yield all of its results. There is no projection on each item, no <code>finally</code> block, nothing after those yields, etc.</li>
</ul>

So, what happens when some code goes and writes the following?

<pre><code>foreach(var n in Foo())
 Console.WriteLine(n);
</code></pre>

Well, the first thing that happens when we reach this statement is to evaluate <code>Foo()</code> to a value. In this case, this creates the state machine that represents the generator of the sequence. We've not actually executed any of the code in the method body though.

Next, we call <code>MoveNext</code>. We hit our first <code>yield</code> block, yield a value, and print it out.

After that, the outer-most level calls <code>MoveNext</code> again. Here our state machine's <code>MoveNext</code> method reaches it's own <code>foreach</code> block. It will, like the <code>Main</code> method, evaluate <code>Foo()</code> to a value, creating a second state machine. It will then immediately call <code>MoveNext</code> on that state machine. That second state machine will reach it's first <code>yield</code>, it will yield the value to the first iterator, which will yield that back up to the main method, that will print it.

Then the main method calls <code>MoveNext</code> again. The first iterator asks the second iterator for it's second item, the second iterator reaches it's <code>foreach</code> method, creates a third iterator, and gets a value from it. The value gets passed all the way up.

As we can see here each time we as our top level iterator for another item the stack is always one level deeper than before. Despite the fact that we're using state machines, and that creating the iterators doesn't consume a lot of stack space, getting the next item in the sequence will consume more and more stack space, until we run out.

When running the code we can see that things work out exactly as described here, and the stack will overflow.

So, how could this possibly be optimized?

Well, what we're hoping to do here is for that top level iterator to realize that when it gets to the <code>foreach</code> that "from now on, the rest of the items in my sequence are identical to all of the items in the recursive call". This does sound a lot like a typical TCO situation.

So at this point we have two issues to solve. First, if we recognize that we're in this situation, can we actually avoid the creation of additional state machines, and thus the continually increasing stack space. It wouldn't be all that easy, likely not quite as easy as traditional non-iterator block TCO. You'd need to set all of the instance fields of the state machine to whatever the instance fields would be of the state machine that would be created if you had called <code>Foo</code>. I'm just going to wave my hands at this point and say that this sounds possible, but not exactly super each.

Then we have the other problem. How can we recognize that we're actually in this position where TCO is valid? We need to be recursively calling ourselves, we need to be doing nothing with that method call other than iterating the whole thing and yielding each item exactly as it stands, we need to not be in a <code>try</code> or <code>using</code> block (else the <code>finally</code> block would be lost), and there can't be any methods after that iteration.

Now, if there were a <code>yield foreach</code> operator then this wouldn't be so bad. You'd just set up the rule that if the very last statement in the iterator block is a <code>yield foreach</code> operator with a recursive call to the method at the very end, apply TCO. Sadly, in C# (unlike some other .NET languages) we have no <code>yield foreach</code> operator. We need to type out the whole <code>foreach</code> operator, while also not doing anything other than yielding the item exactly as it stands. That seems...a bit awkward. 

<h2>To recap:</h2>

<ul>
<li>Is it possible for the compiler to use Tail Call Optimization for recursive iterator blocks?
<ul>
<li>Most likely.</li>
</ul></li>
<li>Is it done by the compiler ever?
<ul>
<li>It doesn't appear so. </li>
</ul></li>
<li>Would it be particularly feasible to add this support into the compiler?
<ul>
<li>Probably not.</li>
</ul></li>
</ul>

tl;dr;

In C#, do you have guarantees that a lazy iterator function that calls nothing but itself and does have a valid recursion exit condition will not cause a stack overflow?

<hr>

Detailed question:

I know that as a rule you don't get guarantees of the Tail Call Optimization (TCO) instruction being generated by the C# compiler (or the JIT), so while you may get TCO, there are no guarantees.

Given this recognition of TCO, I'm wondering if lazy iterator functions (using <code>yield return</code> etc) because of their nature as a coroutine - does each tail call in one even take up stack space? My intuition of coroutines because of their re-entrancy is that each tail call is optimized by default as the ability to jump out of the function and into the next one from the parent's frame instead of creating a new frame seems natural.

Is this behaviour in C#, or do C# iterator functions' recursive calls create a new frame from the current rather than popping out to the parent frame and re-entering with the new parameters?

<hr>

Example:

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

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

My intuition is based off in the above example <code>subPermutations</code> is simply a heaped computation, it seems upon call to iterate it, it can know it's a heaped computation (it is a part of the functions sig that it's an iterator function), and therefore immediately jump out of it's current frame and expanding the heaped computation into a new frame - costing no extra stack space over what was there before the recursive call was attempted...

This intuition may be totally unfounded...

Will a properly implemented recursive lazy iterator function never stack overflow?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

tl;dr;在C#中，你能保证一个懒惰的迭代器函数只调用它自己，并且有一个有效的递归退出条件不会导致堆栈溢出吗？详细问题：我知道通常你不能保证C#编译器(或JIT)生成的尾部调用优化(TCO)指令，所以虽然你可能会得到TCO，但没有保证。鉴于对总拥有成本的认识，我想知道惰性迭代器函数(使用yield return等)是...

一个正确实现的递归延迟迭代器函数会不会出现堆栈溢出吗？-腾讯云开发者社区-腾讯云

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

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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