As far as I know if your recycle bin status wasn't on then file or document you delete is permanently deleted however also if change its status to off from on it empties all of recycle bin which happened to me once and I couldn't recover document back, however I find this link that is claiming you can recover document back.
However if you need more information about recycle bin,
The recycle bin in SharePoint is synonymous to Recycle bin in windows
and helps the users in recovering files which have been deleted
The files in the recycle bin can either be recovered or can be deleted
after a pre defined period of time.
Recycle Bin Stages
SharePoint supports two levels of Recycle bin. The initial or First
level Recycle bin comes in picture when the user deletes an item from
a list. Once the item is deleted again from the First level of Recycle
bin it moves to the second stage of Recycle bin.
Item not available in Recycle Bin
If you try to find an item in the recycle bin and fail to locate it
then you need to verify the following :
The contents in the recycle bin are driven by the access control. The
user who has deleted the content will be able to see the content in
the recycle bin. Other users will not be able to see the items in the
recycle bin. If you have deleted a top level item like a folder or a
list, and try to find a document available at an inner location, then
the item will not be viewable. By default the Recycle bin shows the
top level content and does not have the capability to show the items
in a tree structure or drill down mode. The contents in the recycle
bin contains only the items within the site. A deleted site is outside
the scope of the Recycle bin and is not available for deletion. The
recycle bin contains the items for a pre defined period which can be
set from the Web Application –> General Settings. if the thresh hold
is crossed, the item is deleted permanently.
For More Information check this link OR this link out.