First don't make any changes to your disk. Best situation is if you can boot via a LiveUSB and not mount that disk so as to avoid causing changes to the file system before you get a chance to try repair.
Seems that the best recovery software a lot of people recommend is PhotoRec
Give that a try, it recovers more than just photos, it will recover almost any file type for you. I have used it successfully in the past, after having done pretty much exactly what you're saying here.