Your intuition is correct, but Prolog uses depth first search by design (see SLDNF resolution here) and with good reasons, then that limitation is not easily avoided.
OTOH, Ciao Prolog offers an appropriate extension.
You can simulate breadth first recursion, using a meta interpreter, as done for instance here for a left recursive DCG (left recursive grammars are a common case), but it's not generally an easy way to follow.
IMO the most common extension that could approximate/satisfy your request, is tabling, you can find it in YAP Prolog, XSB, B-Prolog.