Can I recover deleted iCloud contacts?

I accidentally deleted all my contacts in my Mac Address Book, and (since everything is synced with iCloud) that subsequently removed the contacts from all my devices and icloud.com.

I have an iCloud backup for my iPhone from before I deleted my contacts. However, as I understand it, that backup is just a backup of my apps and settings (for example the setting that says use iCloud for Contacts). So when I restored from that iCloud backup, I still didn't have my contacts. I see the reasoning behind this, since iCloud itself is essentially the "back up" for your actual contacts data. But if a contact gets deleted from iCloud (which happened since I deleted contacts on a synced Address Book), how do I recover it?