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...