How can I recover deleted emails

And are you archiving deleted mail? Did you find the mail in Trash? You will need to check with Google to find out if mail is part of the iPhone backup. If you have a recent backup you can go ahead and try restoring the backup to see if the mail comes back, but with an IMAP mail account, I'm afraid once it is deleted from the server, if you don't find it in the Archive folder or Trash, it is gone.

Is your gmail set to send messages that you delete to the Deleted folder, or Archive? Are you using the Gmail app, or are you using the native Mail app on the iPhone?