How to recover iPhone lost contacts?

That depends on where the “master copy” of your contacts reside. Contacts on an iPhone sync from one or more email accounts that you subscribe to. You can go to Settings/Contacts/Accounts to see which of your accounts have Contacts enabled.

If it is specifically iCloud synced contacts see this support article→iCloud: Restore contacts, calendars, and more in iCloud Settings

If it is contacts from any other source, such as MS Exchange, Outlook, gmail, etc you need to check with your account for those services.

It’s also possible that you just aren’t viewing all of your contacts. Open the Contacts app and tap on Groups in the upper left (it will only appear if you have more than one contact account or group within a contact account). Make sure all groups are checked.