Productive Failure is a variant of problem-based learning in which the order of the instruction and problem-solving phase is reversed. The effectiveness of Productive Failure with respect to conceptual knowledge has been demonstrated through a number of studies. The majority of these studies, however, took place in secondary Mathematics classrooms, whereas other studies resulting in less or no support of such an effectiveness were contextualized in other disciplines, including Computer Science, or in tertiary education. This has raised the question of which conditions support or hamper the use of Productive Failure. To deepen our understanding of such conditions, we designed and executed a Productive Failure intervention for a Pattern Recognition class, thus shifting the intervention context into a tertiary setting while maintaining proximity to Mathematics. In an experimental study, we compared the problem-solving progression of students in a Productive Failure setting with the progression of students in a traditional Direct Instruction setting. For this, we analyzed patterns of discourse arising among the participants as well as the longer-term retention of the concepts addressed. The results of our qualitative analysis suggest that, even in a short intervention, Productive Failure can be used to elicit a distinct pattern of progressing though the problem-solving process. At the same time, our study confirmed previous findings that the mode of instruction does not affect exam performance with respect to the specific topics addressed in the intervention. We discuss limitations of the study setting and possible implications for designing future research studies and teaching interventions.