Back them up to your Google acct. that is what I did and i keep it synced so when I change phones they come right back
as soon as I sign in to my Google acct.
This does not help now but will in the future
The only problem with that is there are things you cannot set to Google contacts that you can to phone contacts. I use the Verizon backup assistant for the phone contacts.
If you don't have a copy of your contacts in your S/D card, PC or Verizon Backup Assistant.
There is a usage record that Verizon keeps of everyone you call and everyone that calls you, I gives you the number, location, time and date of usage and call length. This information may allow to recover some important numbers, not all obviously.
There are companies that retrieve erased information from drives and disks, but of course the will charge. Sorry. I know this is not much help, Good luck.
Go into Backup Assistant Trash and you can "undelete" them. That will put them back in your "contacts". Then go to your phone....menu, settings, accounts and sync, backup assistant and it will sync your contacts to your phone. You are supposed to be able to sync from Verizon Backup Assistant to your phone but I have found it doesn't work right very often. Syncing from your phone to Verizon seems to work every time. Hope this helps.