Power recovery for data storage devices with an efficient space trimming technology is shown. A controller scans a non-volatile memory according to a programming order, collects a sequence of trimming information flags, and interprets a sequence of storage information scanned from the non-volatile memory to identify logical addresses and trimming code. Based on the logical addresses, a host-to-device mapping (H2F) table is rebuilt. Based on the trimming code, information of medium-length trimming and information of long-length trimming are recognized from a storage area of the non-volatile memory. According to the trimming information for medium-length trimming, dummy mapping data is programmed to the H2F table. According to the trimming information for long-length trimming, a trimming bitmap (TBM) is rebuilt. Each bit in the TBM marks space trimming of a first length.