In this study, we proposed general goal-setting strategies in a problem of collaboratively achieving a common goal by two problem solvers. As a framework for analysis, we utilized the recursive problem space of the Tower of Hanoi puzzle. We described subjects' goal setting processes by the protocol analysis, and discussed its transition patterns using two indexes for the estimation on the recursive problem space: abstraction level of each goal and distance between two goal states. We identified two kinds of goal setting strategies. One was called the HG strategy (Higher-abstraction-oriented Gradual-goal-setting strategy) in which subjects first set a goal whose abstraction level was the highest then moved to more specific goal settings as the problem was being solved. The second was called the landmark strategy in which subjects used a prominent goal state as a landmark. We confirmed, through our cognitive psychological experiment and analysis, how those two strategies were actually utilized in the subjects' collaborative problem solving processes.