You only need to build the Training grounds. After that, you can automatically recruit more troops as your maximum.
By the way, Recruiters have an undocumented ability to increase the recruit count in the same way, provided that that building is built. So building the upgraded construction for them will increase the recruit count as well. |
