Well, you'd generally remember the last few turns you'd take. The longer the loop, the harder it is to detect. So the algorithm could do something similar - and it would also help with keeping the memory bound sane.