The New England Science Fiction Association (NESFA) has a website with a compilation of references to recursion in science fiction: Recursive Science Fiction[1].
Inception is an exceptionally good example! I'm a big fan of Borges and although I'm sure that there must be one of his stories containing a relationship with recursion, I can't think of one right now.
Infinite Jest by David Foster Wallace (1996) has an interesting structure using hundreds of footnotes some of which have themselves footnotes. The ending is not straightforward and the novel's chronology non-lineal. It contains disgressions on many topics. According to the Wikipedia, in an interview Wallace mentioned that the plotting and notes have a fractal structure modeled after the Sierpiński gasket, suggesting some degree of recursion.
Check The Universe in a Handkerchief: Lewis Carroll Mathematical Recreations, Games, Puzzles, and Wordplays by Martin Gardner. I think you might like it.