Random stepped frequency (RSF) radar, which transmits random-frequency pulses, can suppress the range ambiguity, improve convert detection, and possess excellent electronic counter-countermeasures (ECCM) ability [1]. In this paper, we apply a sparse recovery method to estimate the range and Doppler of targets. We also propose a cognitive mechanism for RSF radar to further enhance the performance of the sparse recovery method. The carrier frequencies of transmitted pulses are adaptively designed in response to the observed circumstance. We investigate the criterion to design carrier frequencies, and efficient methods are then devised. Simulation results demonstrate that the adaptive frequency-design mechanism significantly improves the performance of target reconstruction in comparison with the non-adaptive mechanism.