Students' mental models of recursion at wits
Authors: Sanders Ian Douglas , Galpin Vashti C. 
Published: September 2007

Recursion is a concept which all computer scientists should understand and be able to use but novices find it difficult to master. In the School of Computer Science at the University of the Witwatersrand (Wits) we have for a long time been concerned about how we can assist our students with recursion [4, 1, 3]. One thrust of our research is the study of the mental models of recursion (c.f. Kahney [2]) which our first year students develop.

Most of our students encounter recursion for the first time in our Fundamental Algorithmic Concepts (FAC) course. When we originally investigated the mental models of our students we noted that although many of them seem to develop the viable
copies
model there are still many that develop models which are non-viable (i.e. that cannot be relied on to lead to a correct result) [1]. Thus we adapted the way in which recursion was introduced in FAC in 2003, 2004 and 2005 by introducing more complex recursive algorithms earlier to help in the development of the
copies
mental model. We then compared the mental models developed by the 2003, 2004 and 2005 students to those developed by the earlier group [3]. The results indicate that more of the students were developing viable mental models of recursion and thus that the changes to our teaching were benefitting our students.

In 2006 we changed the programing language in which our students implement algorithms to Python (from Scheme). In essence the programming language was the only change made as the course was still taught in a "functional" style to emphasize the link between the formal specification of a problem, the solution to the problem and the program. We did, however, feel it was important to assess the impact of the change on our students' mental models of recursion. We thus did a similar study on the 2006 students to that on earlier cohorts.

The students' traces from two recursive algorithms were categorised into the mental models previously observed [1,3] by identifying how the student deals with the active flow, base case and passive flow in their trace and then by combining this information into an overall categorisation of the trace for that algorithm. Overall the results are in line with our previous results which showed that the
copies
model is the dominant model for a recurrence relation type of recursive function but that for list manipulation problems some students showed an
active
or
looping
model. These results indicate that our teaching approach, even with the switch to Python, is assisting our students in developing a viable copies mental model of recursion. Such a mental model is more likely to lead to correct traces of recursive algorithms.

An interesting new result was the emergence of a
passive
mental model. Here the students recognised that the recursive algorithm would
somehow
get to the base case and then used the base case plus the implicit definition of the function in the algorithm to build up the required solution. This model may have arisen because the students were given a recurrence in Tutorial 1 and asked to calculate what value would be returned. Solving the recurrence essentially meant working up from the value where the result is defined directly until the desired answer is found. Some students may have adopted this as their model of recursion.