In this paper we present a new algorithm for the recovery of the initial state of a linear feedback shift register when a noisy output sequence is given. Our work is focussed on the investigation of the asymptotical behaviour of the recovery process rather than on the construction of an optimal recovery procedure. Our results show the importance of low-weight checks and show also that the complexity of the recovery problem grows less than exponentially with the length of the shift register, even if the number of taps grows linearly with the register length. Our procedure works for shift register with arbitrary feedback polynomial.