You're pretty much stuck with recovering from backup unless you can get it back from the server side somehow (filesystem tricks, etc). That's pretty unlikely, though, as the physical location on disk where the files were stored have probably already been overwritten by other server activity. Windows only puts things in the recycle bin when deleting from local volumes. Items on network shares are just straight-up deleted.
Assuming this thread is very old, I got here today trying to recover some files. As explained, if like in our case, the samba server is on a Linux server the only options is to recover files there. We've only sometimes had luck with photorec. Requires the testdisk package (apt install testdisk).
Alternatively, we will now be implementing a Network Recycle bin in Samba using the samba-vfs module, which requires assigning a directory on the server en editing the samba.conf