In the future you can use the Portable build which you can place anywhere without any issues.
As for unisntalling it, you can uninstall it manually here's how to do it:
1. Start Recuva.
2. Click Cancel on the Wizard.
3. Now in the main app click Options->General (tab)
4. Enable: save all settings to INI file
(this removes the registry settings)5. Close Recuva.
6. You can now delete the folder it was originally installed in, and the start menu folders it created.
Or this, possibly faster, and probably more thorough:
Use
Revo Uninstaller and perhaps its
Hunter Mode.