A fault recovery scheme of a fault-tolerant processor for embedded systems is introduced in this paper. The microarchitecture of the fault-tolerant processor called RSED is modified from superscalar processor architecture. The fault-tolerant mechanism of RSED is implemented mainly using temporal redundancy technique. Fault recovery scheme is an important part of the fault-tolerant mechanism. In order to resolve the problem of possible single point of failures, a novel TMR approach is adopted to generate re-execution instruction address. Compared with similar works, the fault recovery scheme proposed can recover processor execution more reliably.