A system could still recursively self-improve to solve a vast number of easier problems.

Well, the point here is that it looks like the problems involved with recursive self-improvement themselves fall into the difficult classes. For example, designing circuitboards involves a version of the traveling salesman problem which is NP-complete. Similarly, memory management and design involves graph coloring which is also NP complete.