Does encrypting Time Machine erase the recovery partition?
If you make your Recovery partition as Hidden partition, then the Time Machine wont touch it since it does not see it as available disk space.