Exploring the question of teaching recursion or iterative control structures first
March 9, 2018 at 7:00 am 10 comments
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.
Entry filed under: Uncategorized. Tags: computing education research, iteration, recursion, SIGCSE.
Computing Ed Research - Guzdial's Take 
1.
Alfred Thompson | March 9, 2018 at 10:37 am
OK this will probably get me jumped on but just how important is recursion? As a way of doing iteration it seems awfully complicated and error prone compared to iterative control structures. Sure there are applications where recursion is the best if not the only way to solve some problems but can’t it wait until a second or third course?
When we ask about projects that required recursion for beginners there are few good examples. Towers of Hanoi for example. Even Fibonacci is just as easily solved using iteration as recursion. Exploring trees? Sure. We do that in AP CS but at the HS level at least that is usually a second or third course.
Not teaching iterative control structures would be a huge mistake and if the evidence suggests it is better to teach that first if we are going to teach both the decision seems easy.
2.
Mike Zamansky | March 9, 2018 at 11:42 am
With CS4All and K12 on the table it becomes an even more interesting conversation.
My take on the normal intro courses taught in high school as that they’re supposed to serve two purposes at the same time. They are supposed to give you the basic core knowledge that an educated person should have and also possibly pique a student’s interest and set the stage for more advanced study.
If we’re talking about that type of intro course then you have to ask a few questions:
1. Is it beneficial to introduce recursion early for students who’ll go further.
2. Is it beneficial for those who won’t go on
3. If it is beneficial to one group but not the other, can it be done so as not to do harm to the other group.
It’s also worth looking at recursion away from the computer, call stack, etc. We’re really talking about taking a problem, biting off a piece and handling it and then repeating the process with what’s left until we’re done.
From a higher level point of view, that’s recursion and it’s also a model for how we do lots of things.
We do list processing – to do lists in that manner:
1. do the first thing
2. remove it from the list and repeat
but repeat can be seen as recurse.
I go back and forth on this issue. I think scheme and recursion first works at Stuy but am not convinced it’s right all the time.
3.
gasstationwithoutpumps | March 9, 2018 at 6:15 pm
I’ve never been a fan of recursion first. I think that with iterations like “for x in container:” (to pick a python example), iteration is now much easier to teach first, as we don’t need to be explicit about incrementing and ordering (just not changing the contents of the container inside the loop).
4.
Teach two languages if you have to: Balancing ease of learning and learning objectives | Computing Education Research Blog | June 4, 2018 at 7:01 am
[…] 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. […]
5.
Mark Lewis | June 13, 2018 at 3:03 am
Given the availability of for-each style loops, it seems to me that iteration has changed since those earlier studies. In fact, those loops throw another complexity into the teaching of plain iteration that didn’t exist in C or Pascal. If you go with iteration first, should it be the traditional for and while loops, or should you start with the for-each style, which is generally preferred in real programming because it is less error-prone? It is tempting to say the latter, but that has broader impacts because the for-each loop needs to iterate through something so students have to be introduced to some type of sequence before they can use it.
In the “traditional” approach I believe that most people do iteration with loops first, and only after that has been mastered do they move on to sequences of values. However, the for-each loop, because it runs through a sequence of values, flips that around.
Indeed, a challenge with iteration first is that most languages have 3-4 constructs for iteration: for, while, do-while, and some form of for-each loop. You can pick just one to focus on, but it provides an incomplete picture and might be showing a style that is considered bad for that language. Those choices and the complexity that comes with them don’t exist when you do basic iteration with recursion.
6.
gasstationwithoutpumps | June 13, 2018 at 4:12 pm
Python makes the “foreach” stye the default (to do numeric iteration requires creating a range). I think it is much easier to teach than the C-style for loop, since almost any sort of container can be the object iterated over (character in string, number in range, item in list, item in set, …). Iteration over the elements of some container is a more natural construct for more people than counting out the indices of an array, and is MUCH simpler than recursion.
7.
Mark Lewis | June 14, 2018 at 12:25 pm
This leads to the question, do you teach containers before the for loop, or do you introduce a counting for-loop using the Python range syntax without revealing to them that it has more power than that until later?
I teach CS1 with Scala where the foreach style loop is the only for loop and higher-order methods like map and filter are standard style. As a result, I cover sequences before I cover loops. I don’t have to because I can write a counting loop with for(i <- 1 to 10), but given the power of the collections library, I don't feel a need to rush to general iteration. In Python, you could do something similar by using list comprehensions for a while before going to for loops.
8.
gasstationwithoutpumps | June 14, 2018 at 2:58 pm
I don’t teach beginning programming to undergrads, so I don’t have a tested answer, but I would teach iteration over containers before I would do counting loops, especially since letters in a string are a natural example.
With grad students who were just starting programming, the first loop they saw was “for line in sys.stdin:”
9.
Are you talking to me? Interaction between teachers and researchers around evidence, truth, theory, and decision-making | Computing Education Research Blog | June 15, 2018 at 1:00 am
[…] one is trying to teach both. For me, this is a well-supported statement of theory. I have written about the work by Anderson and Wiedenbeck supporting this argument. I have also written about the terrific work by Pirolli exploring […]
10.
Brian Harvey | November 26, 2018 at 5:10 am
It’s hard for me to imagine a mechanism by which teaching recursion first could make it harder for students to learn iteration. I’d have to see the details about exactly how they taught both concepts to understand this result.
In our high school curriculum (bjc.edc.org) we teach numeric iteration first (repeat and for), before we teach lists. But we sneak in some simple recursive procedures for students to think about. Once we introduce lists, we are very aggressive in using higher order functions, as well as for each. I think the notation we invented for lambda in Snap! is transparent enough in simple cases not to be problematic for students, although we’ve learned that they can get lost if we compose HOFs, and that setting local variables to the result of the first HOF and then using that variable in calling the second HOF is a better way to present the idea.
I have come to think (although not all my BJC colleagues agree) that we should not use recursion to solve problems that are more straightforwardly solved with iteration (or HOFs, which provide abstractions for certain iterative patterns). So I would save recursion for tree-like computations, such as drawing a fractal or computing a value in Pascal’s triangle by adding the two numbers above it.
I think this, teaching high school students, because I’ve heard “why do we have to do it this complicated way instead of using a loop?” too many times, and I’ve come to agree with the students who ask that.
This is very, very different from the way Logo teachers taught younger kids. They used recursion for everything, sometimes without a base case, so (for example) the turtle would move around the edges of a square forever, until the kid typed control-C or whatever the stop button was.
Some of the teachers we work with have said that using HOFs for lists is hard for their students. I want to believe that there’s something wrong with the way we teach them, rather than that kids really can’t understand “add 3 to each item in the list.” Stay tuned for our next revision to see if we’ve solved the problem.