How can I recover a contact that was deleted?

When you look deeply you will find that Contacts are neither stored on an iPhone nor on SIM. They are synced to an email account that you may have added and enabled Contacts. It could be Google, iCloud, AOL, Exchange, Outlook, Yahoo or any Other email client server.

When you enable Contacts in any of the email accounts they are displayed to you through the Contacts App. When you edit these contacts on an iPhone they are ultimately edited on the client-server.

Please see the pic below for a better understanding...

If you are unable to find your contacts which were stored in the email client, then try this --> Restore contacts, calendars, bookmarks, and more using ...

Check if the email account has been removed from the iOS mail app.

Add the email account that stores your contacts in the IOS mail app and enable Contacts.

What is your default Contacts account? If none, please add an email account and enable contacts.

See the pic below

Unlike some Android devices, contacts are neither stored locally on an iPhone nor in SIM. They are synced to an email account that you had Google, iCloud, AOL, Exchange, Outlook, Yahoo or any Other

If you have a corporate email account added through a profile on your device, please check with your organization's system administrator.

If you accidentally deleted your calendars, reminders, bookmarks, or contacts from iCloud, read this support article --> If you accidentally deleted your calendars, bookmarks, or contacts from iCloud - Apple Support

If you do not use iCloud for Contacts you may be able to restore from a backup but that entails resetting your entire device back to the time you made the backup.

Click on this link to learn how to restore your iPhone, iPad, or iPod touch from a backup --> Restore your iPhone, iPad, or iPod touch from a backup - Apple Support

Note that as far as I can tell you are asking about restoring a deleted contact. The Recommended post doesn't actually tell you how to do that, just how to select iCloud for Contacts.