I have delete the Voice Memos app and lost my recordings

No.

Without a backup, the voice memo data is gone forever.

There is no recovery.

The audio data is stored within the app.

It is gone.

Nothing is forever on any computer or mobile computing device.

This would be a good time to start getting a good and semi-regular iDevice backup regimen.

iOS backups can be done to iCloud, iTunes on a computer or by using online, offsite data storage/backup services using online sources, like Google Drive/Photos/Documents, DropBox, BOX, Amazon cloud services, etc. and other similar services.

Sorry & Best of Luck to You!

Depending on when you last backed your device up, you can restore from that backup and see what you get.

Bear in mind it will take your device back in time, so to speak. So say you last backed up a week ago, you may get the voice memos back but will also lose anything you have added to the device since then.

If you haven't been backing up and you deleted the app, when you deleted a message would told you deleting the app would delete it's data, so no, the recordings are gone.