What is the correct way to use async/await in a recursive method?

When I add code to make your example more concrete, I find two possible ways for the recursion to turn out badly. Both of them assume that your data is pretty big and require specific conditions to trigger.

1. If ProcessItem(string) returns a Task that completes before it is awaited on (or, I assume, it completes before the await finishes spinning), the continuation will execute synchronously. In my code below, I have simulated this by having ProcessItem(string) return Task.CompletedTask. When I do this, the program very quickly terminates with a StackOverflowException. This is because .net’s TPL “Releases Zalgo” by opportunistically executing continuations synchronously without regard to how much space is available in the current stack. That means that it will exacerbate the potential stack space issue that you already have by using a recursive algorithm. To see this, comment out await Task.Yield(); in my code sample below.
2. If you use some technique to prevent TPL from continuing synchronously (below I use Task.Yield()), eventually the program will run out of memory and die with an OutOfMemoryException. If I understand correctly, this wouldn’t happen if return await were able to emulate the tail-call optimization. I imagine that what is happening here is each call generates something like a book-keeping Task<string> and keeps generating them even though they could be coalesced. To reproduce this error with the sample below, ensure you’re running the program as 32-bit, disable the Console.WriteLine() call (because consoles are really slow), and ensure the await Task.Yield() is uncommented.

using System;
using System.Collections.Generic;
using System.Threading.Tasks;

// Be sure to run this 32-bit to avoid making your system unstable.
class StreamProcessor
{
    Stream GetStream(string streamPosition)
    {
        var parsedStreamPosition = Convert.ToInt32(streamPosition);
        return new Stream(
            // Terminate after we reach 0.
            parsedStreamPosition > 0 ? new[] { streamPosition, } : new string[] { },
            Convert.ToString(parsedStreamPosition - 1));
    }

    Task ProcessItem(string item)
    {
        // Comment out this next line to make things go faster.
        Console.WriteLine(item);
        // Simulate the Task represented by ProcessItem finishing in
        // time to make the await continue synchronously.
        return Task.CompletedTask;
    }

    public async Task<string> ProcessStream(string streamPosition)
    {
        var stream = GetStream(streamPosition);

        if (stream.Items.Count == 0)
            return stream.NextPosition;

        foreach (var item in stream.Items)
        {
            await ProcessItem(item); //ProcessItem() is now an async method
        }

        // Without this yield (which prevents inline synchronous
        // continuations which quickly eat up the stack),
        // you get a StackOverflowException fairly quickly.
        // With it, you get an OutOfMemoryException eventually—I bet
        // that “return await” isn’t able to tail-call properly at the Task
        // level or that TPL is incapable of collapsing a chain of Tasks
        // which are all set to resolve to the value that other tasks
        // resolve to?
        await Task.Yield();

        return await ProcessStream(stream.NextPosition);
    }
}

class Program
{
    static int Main(string[] args) => new Program().Run(args).Result;
    async Task<int> Run(string[] args)
    {
        await new StreamProcessor().ProcessStream(
            Convert.ToString(int.MaxValue));
        return 0;
    }
}

class Stream
{
    public IList<string> Items { get; }
    public string NextPosition { get; }
    public Stream(
        IList<string> items,
        string nextPosition)
    {
        Items = items;
        NextPosition = nextPosition;
    }
}

So, I guess my two recommendations are:

1. Use Task.Yield() if you aren’t certain that the stack growth of recursion will be interrupted by something else.
2. As suggested already, avoid recursion if it doesn’t even make sense for your problem in the first place. And even if it makes a clean algorithm, avoid it if your problem size is unbounded.