Well, a pretty foolproof method is to build an array of keys to delete, and delete them later.

An array of the initial keys would work. But with the cyclic nature of my data, trying to recurse and push new keys without deleting the ones that have already been processed would be an infinite loop. I could keep a hash of the keys that I want to delete I suppose...

For the same reason, the fact that first() resets the iterator wouldn't even get the chance to be an issue, because if I didn't delete a key as I got it, the loop wouldn't even finish its first iteration. But LanX's answer and input from choroba did lead me to write this version of the fonction which is saner: it removes the key it returns, so the next call won't return it again.