The version of Ubuntu on which Trisquel 5.5 is based has those packages, but Trisquel is missing them. Trisquel 5.0 had them.
I very certain they are not missing because of being non-free. I think they are missing because of errors in Trisquel's purge lists and/or package helpers scripts.
I don't fully understand how those work, but it seems librec0, librec-dev and recutils are purged from Trisquel 5.5 with this script: http://bzr.trisquel.info/ubuntu-purge/trunk/annotate/head:/conf/purge-oneiric
Then there's some helper script which is supposed to get the packages from Debian, but it doesn't: http://bzr.trisquel.info/package-helpers/trunk/annotate/head:/helpers/oneiric/make-recutils
Automatically closed -- issue fixed for 2 weeks with no activity.
Fixed: http://packages.trisquel.info/brigantia/recutils
The issue might have something to do with Ubuntu's package of GNU Recutils depending on libmdbtools, while Debian's package depends on libmdb2. Both Recutils packages depend on the same version of libmdbtool/libmdb2.