You can't recover files on an Android phone without rooting it. That voids the phone's warranty.
Most of the file recovery programs aren't "shady", but there's no guarantee in recovering deleted files in a computer, any computer, due to the nature of computer storage. If another file was stored in the place the SMS file used to be before it was deleted, the SMS file can't be recovered. And whether that happened is purely a matter of chance. So you could root the phone, buy an app (there are no free ones that will recover more than picture and/or music files), then find that the messages you want aren't there.
In the future, use an app like SMS Backup+ to back your messages up on a computer or in the cloud or both. (Any file you don't want to lose should be backed up to at least 2 different devices.)