We can still recover lost android phone data with some android data recovery app, and most of them are very easy to use.
I use gmail and have my phone automatically sync with my gmail contact list. I can add a contact from my workstation and it will show up on my phone pretty much instantaneously. Ditto the other way around, in that changes made on my phone contact list also show up in my gmail contact list instantaneously.
If you have sync your contacts with gmail, you can restore from it. If you need to recover contacts without backup, then you have to download and install professional conatcts recovery tools. Just ask them for help and root your Device first.