The following was posted to the AP CS Facebook page yesterday with the question "What would the answer be?" Things went along just fine for 3 replies of people giving the answer (0123456) until some troublemaker (who would be me) piped in with "Yet an other example of how AP exams are loaded with poor coding practices". And then it got interesting. Recursion seems to stir up a lot of discussion in CS Education circles.
I would argue that this is a poor example of code practice. It is a good, for some definitions of good, example of both recursion and asking students to trace good. That doesn’t make it a good way to get 0123456 output to the command line. At least not in my opinion. Someone raised on functional programming where recursion is a pretty standard way of doing looping might disagree of course. I tend to think that:
for (int i = 0; i <= n; i++) System.out.print(i);
is a lot easier to understand however.
There is a saying that when all you have is a hammer all your problems look like nails. This seems, in a way, to be the case with recursion and loops. If your first tool of choice (or what you have learned first) for iteration is loops you tend not to think of recursion as a solution. Similarly if you start with recursion (as is common with functional programming) you are a lot more likely to look at recursion as a tool for iteration. Personally I struggled with recursion in the beginning. I just couldn’t wrap my head around it for a while. Now I find it really interesting and in some cases very useful. But I prefer not to use it for simple iteration. There is extra overhead involved with all that stack use and I’m still thinking in terms of minimizing memory from my early days when memory was expensive.
But getting back to the discussion I started on Facebook. We are often forced to use code examples that are not ideal coding practice. WE do that to make things clear and to demonstrate specific concepts in a sort of isolation that we might not normally use. We seem to do that a lot with recursion because the example that require recursion tend to be fairly complex. For example traversing trees is an application that recursion is particularly good at but trying to teach both trees and recursion at the same time can be complex. An other frequent example if the Towers of Hanoi which has a complexity of its own. The Fibonacci sequence? Probably better than some but you can still solve it without recursion.
We move on to the question of when should recursion be taught. With functional programming it has to be early. We procedural programming it doesn’t have to be taught early but people disagree on if it should be. I don’t teach it in my first course. Part of that is time – its a single semester course and I can’t fit everything in. Also I tend to think that recursion should be taught in conjunction with other CS concepts like stacks and context switching and memory usage. That is a big pill for a first semester course in high school.
Some might argue that this is all an argument for teaching a first course with a Functional language. I’m trying to make my mind up about that. I’m also wondering if the most important thing a first course does is cover all the key concepts beginners need for some definition of all the concepts beginners need OR is the most important thing for them to learn enough to want to learn more?