Log into your Google account from a browser and select "contacts" from the list of apps (little grid of grey squares). See whether they are still there. If they are then you just need to re-download them. If you can't see them, scroll down to the bottom of the sidebar on the left and look for "trash". Deleted contacts should stay in there for 30 days, so if they were deleted in the last month you can rescue them.
If they've been deleted for more than 30 days then they are gone. I've never seen any reliable evidence that any of the apps out there that claim to be able to recover deleted contacts can do so (claims published by the app providers or by shills who are paid to promote recovery apps in online forums are not reliable evidence).