Did you sync with a computer that you don't usually use? If you lost the app, you lost it's Documents directory, and your recording is gone.
Here's what is supposed to happen;
You're supposed to open iTunes and browse to your device. In the list of apps with the iOS Home Screen style view, there is a section at the bottom to select an Application, and manage it's Documents storage folder.
You do not need to sync in order to view up-to-date information in this screen. You are immediately able to save the data out of the app into a location on your computer.
Unfortunately, if you've sync'ed your phone and lost the app, you've also lost the data from within it. I'm very sorry to say this. There is generally very little probability for data recovery on a Flash Disk device. Not to mention the restrictions of access on a non-jailbroken device (if relevant).
Here is a rough sketch of how you're supposed to follow data management without sync'ing your device. Follow the step numbers in each annotation.

If this screenshot is not large enough to read, you can click on it to view the original size.
~/Library/Application Support/MobileSync/Backupbut it can be quite tricky to find your document there. – Cawas Apr 30 '11 at 15:51