Recursion is a fundamental concept of Computer Science that is difficult
to teach and learn. Students have many misconceptions about recursion
and construct mental models of recursion which are non-viable. A mental
model is a student's mental representation of recursion and it provides
them with predictive and explanatory powers about recursion. A mental
model is non-viable if it does not allow a student to accurately and
consistently represent the process of recursion.

This research analysed traces of recursive programs of first year
Computer Science students at the University of the Witwatersrand. A
trace was defined as a student's representation of the execution of a
recursive program or algorithm. A method to identify mental models from
those traces was developed. The mental models identified were the copies,
loop, odd, magic and null models which have been previously identified,
and the algebraic, step, return value and active models which are new
models. The viability of each of these models and the misconceptions
underlying non-viable models were examined. Suggestions of how this
could inform pedagogy and curriculum were made.

The benefit of this research is that it gives lecturers a greater
understanding of how students learn. Lecturers can use the method
developed to identify their students' mental models and use that
knowledge to provide students with examples and exercises that challenge
non-viable models and thus facilitate the construction of a viable model
of recursion.