This is a general data recovery problem, and not a linux issue.
Usually, overwriting makes it difficult to recover data. So I will not highly rate your chances of getting the data back. Had there been just a format, then you could've got most of the data, but reinstalling Fedora on the partition would've messed things up.
You can try any of the many data recover programs available. You did not mention the file system under which the data to be recovered was under. I suspect, since they were exes, the file system was not ext2. In that case you should be looking for recovery apps that can do recovery from the appropriate filesystem, not ext2. Photorec is a free utility that can recover many file types, but I am not sure exe is one of them.
In any case, avoid any more writing to the partition that contains the data to be recovered. You will need another hard disk/partition to install the recovery software.