The quest for the efficient adaptation of multilegged robotic systems to changing conditions is expected to render new insights into robotic control and locomotion. In this paper, we study the performance frontiers of the enumerative (factorial) encoding of hexapod gaits for fast recovery to conditions of leg failures. Our computational studies using five nature-inspired gradient-free optimization heuristics have shown that it is possible to render feasible recovery gait strategies that achieve minimal deviation to desired locomotion directives with a few evaluations (trials). For instance, it is possible to generate viable recovery gait strategies reaching 2.5 cm, (10 cm.) deviation on average with respect to a commanded direction with 40 - 60 (20) evaluations/trials. Our results are the potential to enable efficient adaptation to new conditions and to explore further the canonical representations for adaptation in robotic locomotion problems.