Safest way would probably be to use the install version to get rid of it. There's also the possibility of renaming the Recuva.exe file to another name (i.e.; Recuva2.exe), and then using CCleaner's registry cleaner to remove the references (if it detects them that is) - this most likely wouldn't be the best approach.
I am not a Portable Purist so I have no objection to, and even welcome, any OPTIONAL and NON-DEFAULT capability for a Portable Utility to be launched via such things as a context menu or a File Association;
BUT
If a newly unzipped Portable Recuva has automatically added itself to a context menu I would suggest reporting this as a bug in