My external hard drive has been formatted. No backup on Time Machine. How can I recover my files?
First step, use a low level tool like dd to make an image of the drive as it exists now, and then stop using the drive. Every second that drive spends connected to a computer (especially a Mac) is a chance for something new to be written to it on top of data you want to recover. All of your recovery attempts should be performed on the image that you make.

Once you have that image, there are a lot of tools you can try to use. 

TestDisk can recover the partition table if that was overwritten. If you had multiple partitions, restoring the table will likely magically and immediately "unformat" all except the first one, because all their metadata will still be intact.

The next thing you want to try depends on the filesystem each (or the only) partition had. There are tools explicitly made for unformatting HFS+, various types of FAT, ext2, etc.

If that fails, or even if it doesn't, the final step is to use a tool that will search through the entire drive, sector by sector, and try to put files back together based on their headers. This is prone to failure in cases of fragmentation, but can often recover things that other methods cannot (including deleted files, fyi). I recommend PhotoRec. You might also try some of the Mac-specific tools covered in this article.