Cognitive radios (CR) are an efficient approach to deploy a secondary network in the vacant portions of the spectrum licensed to primary networks. However, when the quality of the channel being used by a CR user is degraded due to environmental impacts or the return of primary users, the CR should vacate the channel and start a restoration process by searching and sensing other channels. The restoration process objective is to find the best channel in the shortest time to increase the throughput of the CR. We propose in this paper a greedy and intelligent restoration scheme which is triggered in any sensing period, not only when the quality of the channel is lower than a threshold value. Based on the state of the current operating channel, our restoration scheme calculates the optimal number of channels to be sensed in this sensing period and this number is dynamically updated based on the sensing results. This scheme is applied to a new multi-state Markov chain channel model which considers both the appearance of primary users and channel quality degradation. We show that it provides improvements for the CR throughput, compared to the other restoration schemes in the literature that consider a fixed SNR threshold (channel state) to trigger the restoration.