## Posts tagged ‘recursion’

### Teach two languages if you have to: Balancing ease of learning and learning objectives

My most recent CACM Blog post addresses a common question in computer science education: *Should we teach two programming languages in a course to encourage abstraction, or just one? Does it hurt students to teach two? Does it help them to learn a second language earlier?* My answer (in really short form) is “Just teach one, because it takes longer to learn one than you expect. If you teach two or more, students are going to struggle to develop deep understanding.”

But **if your learning objective is for students to learn two (or more languages), teach two or more languages**. You’re going to have to pay the piper sometime. Delaying is better, because it’s easier and more effective to transfer deep knowledge than to try to transfer surface-level representations.

The issue is like the question of recursion-first or iterative-control-structures-first. (See this earlier blog post.) If your students don’t *have* to learn iterative control structures, then teach **recursion-only**. Recursion is easier and more flexible. But if you have to teach both, teach iteration first. Yes, iteration is hard, and learning iteration-first makes recursion harder to learn later, but if you have to do it, iteration-first is the better order.

There’s a lot we know about making computing easier to learn. But sometimes, we just can’t use it, because there are external forces that require certain learning objectives.

*I correct, continue, and explore tangents on this blog post here: https://computinged.wordpress.com/2018/06/15/are-you-talking-to-me-interaction-between-teachers-and-researchers-around-evidence-truth-and-decision-making/*

### Exploring the question of teaching recursion or iterative control structures first

*Someone raised the question on the SIGCSE Members list: Which should we teach first, iteration or recursion?*

*I offered this response:*

The research evidence suggests that one should teach iterative control structures before recursion, IF you’re going to teach both. If you are only going to teach one, recursion is easier for students. If you teach recursion first, the evidence (Kessler & Anderson, 1986; Wiedenbeck, 1989) suggests that it becomes harder to learn the iterative control structures.

*The push back I got was, “Surely, we have better data than 30 year old studies?!?” Here was my reply:*

I agree that it would be great to do these studies again. Given that we have an experiment and a successful replication, it could be an MS or advanced undergrad project to replicate one of those earlier experiments.

For myself, I don’t expect much difference. As you say, student brains have stayed the same. While the languages have changed, the basic iterative control structures (for, while, repeat) haven’t changed much in modern languages from what they were in C and even Pascal. Curriculum may be a factor, and that would be interesting to explore.

Two directions that I think would be great to explore in this space:

(1) **The Role of Block-Based Languages**: As you say, the previous research found that iterative control structures are syntactically complicated for novices. But multiple studies have found that block-based iterative structures are much easier for novices than text-based versions. What if we went recursion->block iteration->text iteration? Would that scaffold the transition to the more complicated text-based iterative control structures?

(2) **The Role of High-Level Functions**: I don’t know of any studies exploring high-level functions (like the ones that Kathi Fisler used to beat the Rainfall Problem, or even map/reduce/filter) in the development of understanding of recursion and iterative control structures. High-level functions have a fixed form, like for/repeat/while, but it’s a simpler, functional form. Could we teach high-level functions first, to lead into recursion or iterative control structures? Or maybe even teach recursion or iterative control structures as two different ways of implementing the high-level functions?

In general, there are too many questions to explore and too few people asking these questions with empirical data. We might rely on our teaching experience to inform our answers to these questions, but as Neil Brown showed us (see CACM Blog post this month that talks about this result), higher-education CS teachers are actually way off when it comes to estimating what students find hard.

* SIGCSE-Members, please consider asking some of these questions on your campus with your students*. There are well-formed questions here that could be answered in a laboratory study that could be encapsulated in a single semester. The students will get the opportunity to do empirical research with humans, which is a useful skill in many parts of computing.

### The need for feedback to improve undergrad CS teaching

Because of the kind of work that we do in my group at Georgia Tech, we visit a lot of computer science classrooms, recitations, and labs. Sometimes what we see is counter to what we now know is effective. Here are two examples from this semester:

- We see small group recitations, where students sit for 90 minutes and passively listen to a recap of the lecture. No peer instruction. We know active learning is better, and we know that it’s even easier to do active learning in small groups.
- We see intro courses teaching recursion before iteration. One of the few replicated results in CS Ed is that iteration should precede recursion. John Anderson and company found that teaching iteration first was better
*even when teaching*, and Susan Wiedenbeck replicated the result (see blog post).**Lisp**

I can’t really blame these teachers. How could they know that there is a better way? *How could we make it better? *By what mechanism do we help CS teachers *improve*? This is a technology transfer problem. The research knows a better way. How do we change practice?

I’d argued previously that we should change promotion and tenure requirements to encourage active learning, and received massive pushback. I don’t think we’ll see that happen anywhere anytime soon. Teachers don’t want to feel “forced” to teach better.

Instead, *what kind of feedback mechanism could we create so that undergraduate teachers learn that they’re not using effective methods? *At my school (and I’m betting at most undergraduate institutions), the only feedback that a teacher gets is from student surveys, course-instructor opinion surveys. That’s not going to help with this problem. How could students know that the class would be better with peer instruction? How could students know that they should have seen iteration before recursion to learn more effectively?

Questions like these have been asked on the SIGCSE-Members list recently. What do you think? What kinds of effective feedback mechanisms have you seen to improve CS teaching? How do CS teachers get informed about research on better practices?

### 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.

Recent Comments