Humans can use recursive combination operation in various behaviors; other primates, however, rarely perform this operation. In our previous research, using an evolutionary simulation of combination behavior, we showed that recursive combination was more adaptive than repetitive combination in cases where the robustness of production or the diversity of products was required. In this research, we examined the evolvability of recursive combination in combinatorial space parametrized by kinds of elemental materials and the number of elements per product. Recursive combination evolved in the region of low kinds of elemental materials and large number of elements per product. This region may be compared with the situation of the middle stone age when invented diversified tools with limited kinds of materials such as stone, bone, and woods. The recursive combinatorial operation could scaffold the evolution of general recursive combination abilities including language, technology, music, and mathematics.