Depends. When were they deleted, and where deleted from? Also, did you have them backed up on say a google account? If yes, then you can get them back from there. If no, then they are pretty much gone.
You can get most numbers you called, or have called you, from your carrier/service provider. They should be in/on your bill either a paper copy or the account online. Most places give you access to that. So the numbers, dates, times and call duration would be there, but not the names. It would be a pain to go through (to say the least) but you could get most of the info that way.