We show that for qubits and qutrits it is always possible to perfectly recover quantum coherence by performing a measurement only on the environment, whereas for dimension d>3 there are situations where recovery is impossible, even with complete access to the environment. For qubits, the minimal amount of classical information to be extracted from the environment equals the entropy exchange.