Instead of going into the low level detail, let me give you a short, high-level understanding of the basics behind the working of any recovery software. I am keeping it extremely simple, so as to make it easy to comprehend!

Let us use the analogy that your hard disk is a book, and the blocks of the hard disk are the the pages of the book.  
Naturally, your data would be the text contained in the pages of the book. 

Now consider a flag – 0 or 1, indicating whether a page of the book is empty or is occupied by some text. The net ‘free capacity‘ of your hard drive is empty is the sum of the block sizes of the pages which are marked as 0 (empty). Makes sense, right?

Firstly, let us understand what happens when you delete a file. Does it vanish in thin air? 

The answer is NO. The file never gets deleted, but what happens is that the pages of the book which contain the data of the file are now marked with a 0, thus designating the space that the file is using as being available for future use when needed. It is no longer ‘accessible’.

N.B. The deleted data is still there, but you have indicated that you are not concerned about it, since you have deleted it. In course of time, the data in this space can be overwritten by other files, and thus compromising the original file that you had you deleted and intend to recover.

So now, how does the recovery software work?

In layman’s term, data recovery software scours the hard drive to look for the pages marked with 0s to locate any recoverable data, piecing it back together and providing it in a salvageable format. 

While deleted files are inaccessible and are in danger of being overwritten, they can often be recovered with professional data recovery tools. 

N.B. No data recovery software is perfect; if a file has been partially overwritten or otherwise compromised, the chances of any usable recovery are low, even with the best recovery software. But if it hasn’t been too long since you deleted the file, the chances of complete recovery are pretty good!

Hope that helps you understand data recovery software better