Article: Mental Models of Recursion Revisited
Context
It is generally accepted that students find recursion a difficult concept to master. They often do not understand recursive algorithms and do not generally develop recursive solutions to problems even if such solutions are the best way to solve the problem. At the University of the Witwatersrand (Wits) we recognise the importance of students coming to terms with recursion and thus start to introduce recursive algorithms at first year level. Over the years we have had some success with this approach but there are still students who do not understand recursion. As part of our efforts to help our students master recursion, we decided that it would help us teach the concept if we knew how our students thought about recursion. This led us to Kahney’s work on mental models of recursion.
Theoretical frameworks
The term “mental model” is one that is used by cognitive psychologists to define cognitive representations of knowledge. A mental model is the understanding that an individual learner constructs. Kahney defines recursion as “a process that is capable of triggering new instantiations of itself, with control passing forward to successive instantiations and back from terminated ones”. A viable mental model of recursion features both flows of control. Kahney called this the copies model.
Research Questions
In our work we were thus trying to answer the question “What mental models of recursion do Wits first year computer science students develop?”. In essence we were interested in determining whether our students developed the same mental models as those identified by Kahney or whether they develop different mental models. In an earlier paper we reported on a study of the mental models developed by the students in the 2000, 2001 and 2002 first year classes. In this paper we reported on extending the study by considering the mental models of recursion developed by the 2003, 2004 and 2005 first year students. This paper also looks at the whether some changes that we made to our teaching – the main change being introducing algorithms which explicitly require the students to cope with the passive flow (unwinding the recursion) much earlier in the curriculum – had any impact on the mental models of recursion which our students developed.
Methodology
In our first year course the students are expected to understand but not necessarily develop recursive algorithms. We show them a number of recursive algorithms and expect them to be able to predict the results of executing the algorithms. In tutorials, tests and examinations we expect them to be able to trace the execution of given recursive algorithms. The methodology that we applied for both the earlier paper and this one was based on using students’ answers to an examination question which asked them to trace the execution of a recursive algorithm. We collected the traces for each question together and then coded each trace into categories which defined characteristics of recursion such as the active flow, the passive flow and the limiting case. The students’ mental models were identified from the combination of categories a trace exhibited.
Findings
We found that our students developed the same mental models as the students in Kahney’s work, i.e. the copies, looping, magic/syntatic and odd models, but also developed models which we termed the active, step, return value and algebraic models. Of the models, only the copies model is always viable (a correct picture of the recursive process). The active and looping models can, however, be viable in some cases and were used by some students to accurately predict the output of recursive algorithms where the solution to the algorithm is not built up during the passive flow stage. It was interesting to note that some students who adopted active or looping models for some traces switched to the copies model when necessary – this seems to indicate a deeper understanding of the recursive process.
Future Work
This work has given us some understanding of the mental models that our students develop and has allowed us to make some changes to the way that we introduce recursion in our first year course. There are, however, still some students who do not come to terms with the concept and we need to find a way to assist them. There are also students who can effectively trace the recursive algorithms but cannot produce recursive solutions to problems and seem not to have a deeper understanding of recursion. We need to find out why these students cannot make the transition from tracing recursive algorithms to developing their own and then we need to find ways to assist the students with this next step.
Author 1: Ian Sanders [email protected]
Author 2: Vashti Galpin [email protected]
Author 3: Tina Gotschi [email protected]