Recovery is analogous to setup, where it's a source register feeds a destination register, the only difference is that it feeds the asynchronous port(clear or preset) of the destination register. For a simple example, a 10ns clock domain might have a register called areset that fans out to the aclr port of all registers in that domain. When that source register goes from 1->0, releasing the destination registers from their reset state, we want that signal to hit all the destination registers within 10ns. What that means is that the clock edge at time 0ns, they will all be held in reset, and at the next edge they will all be released from reset and see the clock.
If any registers fail, i.e. have a delay to them that is longer than 10ns, than those registers will still be in reset for that clock edge. If they are part of a state-machine or some control logic that "goes" on the first clock, this can cause serious issues, because your device comes out of reset over various clocks. It's also troublesome in that it causes "random" failures. Meaning, if timing analysis says the path to some registers is 12ns, which is a failure, some devices might be much faster than that and still work, some might be longer. It can be a nightmare to debug.
The reason it's called Recovery is that it describes how the destination registers(i.e. all the registers in this domain) recover from the reset state.
Glad to hear your making progress.