Students' mental models of recursion at Wits (poster)
I. Sanders and V. Galpin
Proceedings of the 12th annual SIGCSE conference
on Innovation
and Technology in Computer Science Education, Dundee, Scotland,
25-27 June 2007, 317
Abstract
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.
References
[1] T. Götschi, I. D. Sanders, and V. Galpin. Mental
models of recursion. In Proceedings of the 34th SIGCSE
Technical Symposium, pages 346-352, Reno, Nevada,
USA, February 2003.
[2] K. Kahney. What do novice programmers know about
recursion? In E. Soloway and J. Spohrer, editors,
Studying the novice programmer, pages 315-323. L.
Erlbaum, Hillsdale, New Jersey, 1989.
[3] I. D. Sanders, V. C. Galpin, and T. Götschi. Mental
models of recursion revisited. In Proceedings of the
Eleventh Annual Conference on Innovation and
Technology in Computer Science Education, pages
138-142, Bologna, Italy, June 2006.
[4] D. Wilcocks and I. D. Sanders. Animating recursion as
an aid to instruction. Computers & Education,
23(3):221-226, November 1994.
Full text at ACM Digital Library
Poster - PDF
Back to Publications page