Async, recursion, and some weirdness in design of asynchronous API in C#
Time for a bit technical post here :)
One of my typical interview questions implies a DFS tree traversal, and a typical solution for it involves recursion. And when I see a recursive solution, I typically ask: “What are some limitations of this approach?” If the answer lists possible StackOverflowException, the next question usually is: “What is the easiest way you know to get rid of recursion here to overcome all these limitations?”
The question is not language-specific, but since last year I interview mostly .NET developers, in 99% cases it’s about C#.
So what’s the easiest way to get rid of recursion in C#? Let’s look at this code:
It’s probably the simplest example of recursion, and it fails with stack overflow.
One of seemingly simplest ways of getting rid of recursion here is to rewrite this code with async/await:
As you see, all I did is added async/await. It’s pretty logical to expect it’s going to work, coz we are going to use a chain of delegates notifying about Task completion to “move” our regular call stack to the heap. Nevertheless, it will fail with stack overflow exception as well.
The solution is to add two more additional calls:
I added await Task.Yield() twice — once on entry, and once on exit. And removing any of these calls will lead to the same issue.
Knowing why this happens in C# is pretty important for understanding the way async/await works. It also worth to note that C# is pretty unique in this sense — e.g. this code works absolutely nicely in F#:
If you know why these two Yields are necessary in C# code, feel free to add a comment right to this post (or on Facebook). Next time I will share my discoveries on that — so to be continued :)