Recursion–How and When to Teach

I’ll start with a confession. Recursion is one of those concepts that I struggled to understand in the beginning. Was it me or was it how it was taught? An open question that I don’t want to look for blame. A recent article by  Shriram Krishnamurthi, CS Professor at Brown University, called How Not to Teach Recursion suggests that maybe I was taught badly and worse still that I taught it badly.

Adam Michlin wrote an interesting, related, post called Why you shouldn’t teach recursion (yet)

The teaching of recursion is one of those topics that really gets people talking. I hope thinking as well. Certainly I have been thinking about it lately.

Teaching it early, teach it late (as Adam suggests), not teach it at all? All question people ask and answer differently.

My key takeaway is that recursion has to be the natural solution to a problem for it to really make sense to students. Navigating a tree structure, file directories for example. This implies a prior understanding of the related data structure is also required.

Some languages and teachers use recursion for iteration. I guess for some that feels natural but it never has for me. Perhaps I am to old school and too deep into for statements and while loops. When I started programming there were languages that didn’t support recursion at all!

I have had several students discover recursion (and stack overflows) by having the main function call itself. Very instructive.

I’ve been programming for about 48 years now and very seldom have I had a real need to use recursion. By need, I mean that was the bests and only way to code a solution. One time I wrote a really cool recursive method which I was writing code for a living. Upon code review the rest of the team made me rewrite it as an iterative method because they decided it was too complicated and no one else wanted to try to debug it some day. Most of the teach was fairly young and were recent graduates from top CS universities too!

How important is recursion really? The AP CS A exam tests it lightly in the multiple choice questions (as I understand it). The AP CS Principles didn’t test it at all. SO if you are basing decisions on those exams (which is a whole other problem IMHO) its not that important. Do an advanced data structures course on the other hand it is probably fairly important.

If you are teaching it though I think the important things are outlined in Shriram ‘s article. The popular examples are problematic at best. From the post:

Where does recursion come from? HTDP argues that it arises from self-references in data. That is, recursive data suggest recursive solutions. This is the key insight you need for understanding recursion. Not only does it make sense once you think about it, it also demonstrates why most other approaches to teaching recursion are essentially incorrect.

But do read Shriram’s article. He explains it much better than I can.

[Edit: Mike Zamansky gives some thoughts on teaching recursion at On Teaching Recursion
Worth the read. ]

[Edit: Michele Lombardi gives here thoughts at Chiming in on Recursion