Recover a deleted contact without iCloud backups
Follow this:


Logon to iCloud.com
Go to Settings
At the bottom left you will see Advanced and "Restore Contacts"


From there you will be able to restore a previous backup that iCloud has done.