When you delete a file, what happens is that the OS just frees the place on the Hard Disk - the data isn't overwritten unless you use "secure erase", but all meta-information is lost - eg the filename and the folder it was associated with. Now, unless you have written new data onto the HD and the new data has used the space from a file you've 'deleted', you'll be able to recover the file.
The file recover program works by scanning every sector of your HD and tries to recreate files from the data still present on the sectors.
Think of your HD as a book with contents, chapters and sub-chapters. When you get it, all the pages are blank. When you create a folder on the HD you are initiating a new chapter; when you store a file you write a sub-chapter. When you erase a file, you just erase the entry in the content section of the book, but the text on the pages is still there. Now, when you write a new sub-chapter, you seek for the first free page - if the page has text on it, you erase it and write new text on it, then you repeat for as many pages as necessary. Now, you have to be aware of two things: the pages don't have to be conseccutive and only as many pages as are needed are written to So let's say you have 2 chapters with 5 pages each, and then erase them. If you subsequently write a new sub-chapter 3 pages long, you might be able to recover 2 pages from one file and the whole of the other file; if you write a new sub-chapter 7 pages long, you might be able to recover 3 pages of one file. (Actually, it's more complicated than this, but for simply understanding the basic principles this will be sufficient.)
Now, in order to do their magic file recovery programs can't write to the HD being searched as there's a danger of overwriting data that can belong to file that has to be recovered. Thus the need for an external HD.
When the recovery process is over, you'll just have a lot of generic files - the recovery program is able to find out which type of file they are but neither their names nor where they were stored.
So: get that external HD as the program says and as you have been advised to here -OR- consider your files lost forever !