Exploring the question of teaching recursion or iterative control structures first

March 9, 2018 at 7:00 am 3 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: , , , .

The state of the field in pre-college computer science education: Highly recommended Google report Announcing Barbara Ericson’s Defense on Effectiveness and Efficiency of Parsons Problems and Dynamically Adaptive Parsons Problems: Next stop, University of Michigan

3 Comments Add your own

  • 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).


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Trackback this post  |  Subscribe to the comments via RSS Feed

Recent Posts

March 2018
« Feb   Apr »


Blog Stats

  • 1,510,633 hits

Enter your email address to follow this blog and receive notifications of new posts by email.

Join 5,265 other followers

CS Teaching Tips

%d bloggers like this: