Why You Shouldn’t Teach Recursion (Yet)

Picture taken from this presentation

My esteemed colleague Shriram Krishnamurthi has written an interesting draft blog post on How Not to Teach Recursion that details some of the common, perhaps misguided, ways computer science teachers teach recursion.

Let me start by saying that I agree with much of his criticism. Fibonacci is a contrived example and ignores the horrible computational complexity of the recursive solution compared to the iterative solution. Euclid’s Algorithm, best left for a dedicated course in Cryptography, becomes an out of context example and I truly do not understand why anyone would care about Towers of Hanoi. My own education in recursion began by being required to implement the Knight’s Tour Problem on a chess board in Pascal and I still bear the unseen scars to this day.

Regarding recursion versus cyclicity, which is a very valid criticism, I make a point of always teaching stacks before teaching recursion. When students understand stacks, it is much easier to explain why unbounded recursion is different than cyclicity. It also helps them to understand a computer security term like “smashing the stack” or why Stack Overflow is called Stack Overflow (they never use that website… ahem). With a proper understanding of stacks, the “dumb” jokes become not so dumb and do serve to elucidate learning.

Now let’s talk recursion in context of AP CS A, where things are much worse

In AP CS A, recursion is only tested on the multiple choice portion of the test. Let that sink in. As bad as any of the above examples, not a single one will appear on test. And what will appear on the test will likely look something like this.

But it gets worse. The multiple choice test is timed and the students have to do a certain amount of problems in a relatively small amount of time. Correctly tracing mystery recursion problems takes time and doing that in a time crunch, is quite frankly, a good way to get students to absolutely abhor recursion for life. Frankly, Towers of Hanoi and Euclid would be an improvement.

My preference would be to wait to teach recursion until the students have significant experience in data structures, at least stacks, queues, lists, and trees. The beauty that is the recursive algorithm for walking a tree is where I would want recursion to be introduced. Moving recursion out of AP CS A and collegiate CS1 into data structures is not likely to happen any time soon, so I have come up with a compromise in my own teaching.

While I no longer teach AP CS A at the high school level for this and many other reasons. I do use the Fibonacci example, although I quickly explain all the limitations in context of the computational complexity I like to first teach (that is not part of the AP CS A curriculum). Students do first know stacks and lists (not so much trees) and I do a bit of hand waving explaining recursion and walking trees. I would prefer to leave recursion out entirely, but know all too well what waits them in college.

I tell them that, done properly, recursion is a beautiful thing. Which, I hope, will help them weather the storm to come in college that is Towers of Hanoi, Knight’s Tour, and Euclid.