One Thousand and One Nights, that is the oldest.

Cloud Atlas by David Mitchell is pretty close

Gravity's Rainbow by Thomas Pynchon.

Subtle, but I thought of another one. Gene Wolfe's The Book of the New Sun (five parts) -- see: https://en.wikipedia.org/wiki/The_Book_of_the_New_Sun

I've seen it described as a "palimpsest" -- where a page has been erased to make room for more writing, but if you're very careful, you can still read the original. At first glance, it appears to be a bog-standard fantasy travelogue, but as you read, you realize this thing is an onion with layers hidden underneath. It becomes a puzzle decoding the whole thing -- a fun puzzle mind you, because there is still an entertaining surface level adventure going on -- and as you peel back the layers, you realize that time travel is in play and the whole story becomes much more interesting. There's a bunch of other sources non-linearity in it too, mostly due to memory transference. While you're reading, you should be asking yourself "who is Severian?"

You could spend your whole life studying this thing.

You can try 7 1/2 Deaths of Evelyn Hardcastle by Stuart Turton! I really liked that one. It’s more Groundhog Day but with a bit of a twist on each iteration if that makes sense. I don’t want to spoil too much but it was a wild ride putting things together.

Dhalgren by Samuel Delaney is exactly what you are looking for.

I can't think of any directly recursive books, the closest I can think of is

By dakota krout, keep in mind, knowing this detail spoils a fairly big reveal in the series so proceed at your own risk.

There are many time-loop stories in speculative fiction. Hell, there's like a thousand episodes of sci fi TV with this premise.

But if you're looking for a good one, try Hyperion (and Fall of Hyperion). The first book can standalone, but the second book gives you a more satisfying answer to your question. It is told in a Canterbury Tales style, with multiple converging retrospectives. But the principle antagonist is time itself. Very fun read.

Recursion by Blake Crouch

Thanks for the suggestions! Some have been already on my reading list, because they went into that direction and others I've added. I'm not sure, if my wording was understood 100% and if these books are what I'm looking for, but I guess the acknowledgement of the recursion would be a surprise element anyway. Thanks again!