Well, if you had the phone synced to a google account, and it was updated regularly, then you might be able to find them there.
If not, then once deleted they are gone. You 'may', and I do mean 'may', be able to find them using one of these recovery programs, but there is no guaranty it would help.
Your other option is to go into your account, on your carrier/service providers web site and you should be able to find all numbers you have called, gotten calls from, texted or gotten texts from. While no other info would be present, you would be able to locate many numbers.
There are a few apps/programs out there that 'may' be able to help you recover the data.
A few of the programs you could try would be... DiskDigger, MobiSaver, Android-Recovery and Tenorshare. They are all data recovery apps/programs. There are many others out there, so check around and see which you would rather try. There is also one called RECUVA, that I have heard is free, which you could try.
One important note though, most of these programs are not free. They may say they are "free" or have "Free Trials" and "Free Downloads". Yet to actually recover your data, and get your files back, you may be have to purchase the program/app. Just so you know.
NOTE: For future reference, I really would suggest backing up your data to a computer or cloud. Often. Better to spend the time doing that, rather than to be out all that stuff if the phone dies, things get deleted/erased or it gets stolen.