You can go both ways. Sometimes, just creating a new auxiliary class and leave it as an empty shell for the time being is a good approach.
However, the main benefit of TDD is feedback about your code, so if this happens to you a lot, you should stop and consider what this tells you about the design of your API.
Still, there's nothing inherently wrong about this, because it also depends on your overall approach. If you're doing Outside-In TDD this would tend to happen a lot, because you start at the abstract level and work your way down (and the lover-level classes don't yet exist).
On the other hand, if you do Bottom-Up TDD, this shouldn't happen too often, because you start with the building blocks, and then compose higher-level classes from those building blocks.
In any case, the 'recursive' approach is an example of a situation where using Git really shines, because every time you experience that you need to write another test before the one you're currently writing, you can go
git stash
and then write the new test. When you're done with the new test, you can go
git stash pop
to return to the original test. You can do this recursively, so it helps you keep track of your thoughts.