A self-referential situation: where cause chases effect until it's hard to find out which preceded which, if indeed this is the case.
A simple recursive situation is the one where both Trolls and Dwarfs fervently believe the other one ambushed them first at Koom Valley. Unless you accept the simplistic and frankly hard-to-believe explanation that both sides ambushed each other simultaneously, you have to consider that (i) one or both sides were mistaken, or have selectively interpreted historical event to reinforce tribal belief that the other lot are not to be trusted: or (ii) some mucking around with Time, memory or both, has taken place.
Mrs. Evadne Cake also suffers from recursion. Her psychic ability has now evolved to the point where she is capable of having a premonition that she will have a premonition, which makes keeping track on what the premonition tells her people are about to say twice as difficult. Yet she still has to follow through the logic, eg by going up to Mavolio Bent's room to ask him if she has already been up there to say some gentlemen are at the door to see him, or she'll still get the headache that happens if people viciously don't provide their part of the conversation after she's premonitted it.
Recursion on the grand, indeed the cosmic, scale, has happened/is happening/will happen/might have happened like this:
In The Science of Discworld, the Wizards created Roundworld as an experiment in how a world without narrativium can survive. (Well, Hex did the actual creating, to divert a critical magical mass from causing terminal damage, and the Dean actuated it by sticking his hand in and wiggling his fingers. But that's beside the point.) As the wizards watched, the Roundworld universe evolved, to a point where the planet brought forth human intelligence. One small but significant fraction of this intelligence called itself Terry Pratchett, and one day he came accross an old myth about a flat world, borne through space on the backs of four elephants who in turn were standing on the back of a turtle. And he thought, What if this were true? and set about developing his ideas.
At this point, Hex rang a bell and announced Recursion is complete, but nobody was there to hear or understand...