Was iPhone always syncing with a Mac ( signed in with same Apple ID and password on the same network ) Set up and use iCloud Contacts - Apple Support and you never deleted the contacts from any where ( from iPhone / Mac and iCloud.com ) , them in that scenarios the contacts will always be saved even the versions are changed .
If you delete contacts from iPhone or Mac they are immediately erased and not moved in recently deleted so if you go to advanced section the contacts will not be found .
If you were using a single iPhone and it never synced with Mac and you delete the contacts from device itself they are immediately erased and can't be recovered , as iPhone data base is very less compared to Mac .
this article is for Mac for restoring deleted contacts from advanced section with previous versions If you accidentally deleted your calendars, bookmarks, or contacts from iCloud - Apple Support
It doesn't matter you have turned on contacts box in iPhone / Mac , they will only sync the contacts with iCloud , the contacts deleted only from Mac are kept till 30 days after that they are erased permanently from Mac / iCloud and will never be recovered .
See the thread https://discussions.apple.com/thread/252621643?answerId=254939633022#254939633022