Sharepoint - Sharepoint REST api - Recursively fetch all folders in a document library -

I think you should use CAML query with REST API.

Here you can find your solution on this answer by Vadim Gremyachev

Sample code provided by Vadim Gremyachev:

function getListItems(webUrl,listTitle, viewXml) 
{
    var url = webUrl + "/_api/web/lists/getbytitle('" + listTitle + "')/getitems"; 
    var queryPayload = {  
               'query' : {
                      '__metadata': { 'type': 'SP.CamlQuery' }, 
                      'ViewXml' : viewXml
               }
    };

    return $.ajax({
           url: url,
           method: "POST",
           contentType: "application/json;odata=verbose",
           data: JSON.stringify(queryPayload),
           headers: {
              "X-RequestDigest": $("#__REQUESTDIGEST").val(),
              "Accept": "application/json; odata=verbose"
           }
     });
}

function getAllFolderItems(webUrl,listTitle)
{
    var viewXml = '<View Scope="RecursiveAll"><Query><Where><Eq><FieldRef Name="FSObjType" /><Value Type="Integer">1</Value></Eq></Where></Query></View>';
    return getListItems(webUrl,listTitle,viewXml);
}

Your query may like:

<View Scope="RecursiveAll">
     <Query>
         <Where>
            <Eq>
               <FieldRef Name="FSObjType" /><Value Type="Integer">1</Value>
            </Eq>
         </Where>
     </Query>
</View>