tl;dr
Thinking of a recursive call as the creation of and delegation of control to a new instance of the recursive function is vital to complete understanding and correct use of recursion. Prerequisites for this are solid understanding of function calling, parameter passing and embedded function calling. Instructors need to adopt different ways of teaching to match the understanding of their students.

Oh, and recursion is really cool.

While researching common misunderstandings of recursion for a conference talk proposal, I came across some interesting research by Tina Götschi. (Mental Models of Recursion )

Tina Götschi sought to uncover what kinds of mental models were used by computer science students and to evaluate the viability or usefulness of those models. Her goal was to find ways to improve upon current teaching methods and computer science curricula. As a first step, she used a written test with three parts. The first part gathered background information on the students, seeking to capture their previous programming experience. The second part asked the students to define recursion in their own words. The third and final section required the students to trace through four different recursion problems, writing and drawing out their process.

Mental Models Used

Prior to her work, previous research had uncovered five primary  categories of “mental models” used by students, children and programmers to conceptualize and understand recursion. These models are copies, loop, magic, odd, and null.

The copies model (which is credited as a signal of “expert” understanding of recursion), reflects that each recursive call is in essence a copy of the method instance. When the method is called recursively, a new copy is instantiated and the active control of the program is passed to this new instance. Once the final instance reaches the base case, then control is passively returned through the instances up to the originating recursive instance. Based upon Götschi’s research, this model is the only model which is viable for all types of recursive programs.

The remaining models can be somewhat viable for certain circumstances. The loop model reflects a student’s attempt to break down a recursive program as a series of iterations. The magic model refers to student who deduced their understanding of a program by treating the recursive call as a form of “syntactic magic.” This shallow understanding of the recursive program was only viable when used in the context of a familiar, actual problem (such as calculating a Fibonacci series) and not with “nonsense” programs that only manipulated the parameter with no real purpose.

The so-called odd model captured mental models that did not fit into any of the above categories. Null indicated that the students either did not form a mental model at all or at least were unable to articulate and demonstrate it in the testing.

Götschi’s research revealed additional models, as well: the algebraic (interpreting the recursive call as an algebraic formula), step (similar to the loop model), return value (based on a misunderstanding of parameter passing) and active models (which leaves out the passive control needed for the copies model.)

Götschi’s Conclusions

The primary goal of Götschi’s research was to identify ways in which instructors could improve upon how they teach the concept of recursion. As a first step, students need a solid understanding of function calling and parameter passing. Deficits here lead to faulty mental models that can work for some recursive problems but not all. This partial understanding then cements the wrong mental model, which can be difficult to overcome. Götschi recommends then explicit instruction in embedded function calls before attempting the topic of recursion. She also recommends frequent assessments to ensure correct understanding.

Finally, Götschi’s research emphasizes the importance of covering a full range of recursive program types. The non-viable models mentioned above work for some problems. Waiting until students have locked onto non-viable models delays the moment when they must adopt new ways of approaching the problem.

Other Thoughts

Given the large numbers of computer science students who develop faulty mental models of recursion, it’s unsurprising how difficult it can be to teach recursion. In Götschi’s research, only between a quarter and half of the subjects developed viable mental models of recursion. Given more experience, it is possible that some will develop a deeper understanding. Given the persistence of mental models Götschi observed, however, it is likely that many will not. Given that the next cohort of teachers will come from the current generation of students, there is risk that this misunderstanding will be carried forward.

What to do? New methods of instruction could help. Götschi calls for instructors to use student assessments as a pivot points: if students don’t understand the topic, a different point of view is required. “[Teaching] unvaryingly to each and every student will not mediate learning as well as one who is continually gauging his or her learners’ understanding.” Götschi and others point to visualization and dramatization of recursive methods (instead of the staid “Russian dolls” metaphor) as useful tools for developing student understanding.

What do you think?

Do you use a mental model unlike any of those listed above? Do you have confidence in your understanding of recursion? How would you explain it to a novice? Do you think it’s even possible?