Recursion by Pirolli (1991)
I heard Greg Wilson’s request for me to talk about the papers I’m reading (especially since I owe him a chapter which is a review of literature), so I thought I’d talk about one that Barb and I have been thinking a lot about lately: Effects of Examples and Their Explanations in a Lesson on Recursion: A Production System Analysis by Peter Pirolli (1991), in Cognition and Instruction, 8(3), 207-259. In this paper, Pirolli describes two studies where he explores what kind of examples are useful in learning to write recursive functions, and how the characteristics of the example influences what errors students make when they write their own recursive functions. It’s a dense paper, with some sophisticated quantitative analysis on error rates.
I was interested in this paper as one of the first in computer science to build upon Sweller’s worked examples research. Pirolli was explicitly trying to understand the role of examples in problem-solving and about usefulness of different kinds of examples. The first interesting tidbit that I got from this paper is how many examples Pirolli sees as necessary to learn the basics of the language. He’s teaching students to write recursive functions with a version of Lisp (called “SIMPLE”) with only 7 primitives. Here’s an example SIMPLE program:
During the training phase, when he’s just bringing people up to speed on these primitives, he provides 8 examples for each of the 7 primitives. 56 individual examples (where he shows the primitive applied to a list, the student is asked to guess the result, and if fails, the system provides the result) is a lot of examples just to get students familiar with the language. When you teach CS1, do you show 8 examples of for loops before students try to use them in an assignment?
The most interesting lesson I learned about recursive examples from this paper comes from the two conditions in his first experiment. In one condition, the recursion examples that students work through are about how to write a recursive function (e.g., “here’s the base case” and “here’s how it recurses”). In the other condition, the recursion examples are about the dynamics of how it works (e.g., “first there’s this call, then the same function is called but with this input, then the result is returned…”), like this:
Here’s the bottomline of what he finds: Getting students through the “how to write” examples took on average 57 minutes, while the “how it works” examples took an average of 85 minutes. There was no statistical difference in performance on a post-test on writing recursive functions, though the “how to write” group had slightly fewer errors.
Even more intriguing is the discussion where Pirolli relates these findings to others in John Anderson’s group at the time which suggest, “that knowledge about how recursive functions are written is different from knowledge about how they work” and “that there is little transfer of how-it-works knowledge to function-writing tasks and, more interestingly, that extensive additional practice with simulating the evaluation of programs yields no significant benefit in debugging tasks when compared with extensive practice just coding programs.” Writing code and tracing code are completely different tasks.
Barb is helping to teach an AP CS class this semester, and she’s teaching recursion right now. She’s basing how she teaches recursion on Pirolli’s results. Her first activities have the students looking at recursive functions and highlighting the base case and the recursive call — just figure out the structure. Then they write some recursive functions. This is Pirolli’s Experiment #1 process, which takes students less time, giving them an early success with less frustration. Next, she’ll get into debugging recursive functions, which Pirolli suggests is really a different task entirely.
Pirolli’s paper isn’t the definitive statement on teaching recursion or using worked examples. If it was, he wouldn’t have gone on to write several more papers, including several with his students at Berkeley on using examples to learn recursion. It is a nice paper that provides good evidence with some practical implications for how we teach.