Some (most) CCs will allow prior recurring charges to continue with an old/lost/stolen CC number for some period of time (potentially until the expiration date) so you can avoid that headache.
In the case of my AmEx, I have some monthly charges still using an old number from 3 years and 2 stolen cards ago. Discover used to offer this too, though I don't know if they currently do.