It is never good to format hdd first before recover. This bad option is only used by poor man who do not have access to the right tools.
So the answer is "directly recover without formatting".

Sorry for not being able to answer your other question. I have limited experience when it comes to fully automated data recovery software. You can try all free software from links in this thread, one by one.

Basically, I do all non-hardware fault data recovery using WinHex, which I call semi-automatic tool; this requires knowledge in file systems (NTFS, FAT). You can contact me if you need expertise to have a human look at the corrupted file system.