As far as I know they build up a graph of the cell execution order, so recursive loops are quite easy to find.

Finding cycles in a graph is not that simple though. I'd expect they just keep a few state bits in each cell and when a cell that's marked as being in the process of calculation gets hit again as a dependency you've hit a cycle.