Mike Zamansky has an interesting post on recursion. The question at hand is whether it makes sense to teach recursion to beginning programming students. Zamansky was a high school CS teacher for many years and now he’s involved—at least in part—with teaching those who might want to become high school CS teachers themselves. It’s no surprise, then, that the beginners he’s concerned with are high school students.
Like most of you, I have no experience teaching high school students so I’m not competent to offer an informed opinion on the question. Nonetheless, I was struck by some of the comments to the post. Most were from HS CS teachers who also had an industry background before going into teaching. What these commenters all said was that they seldom, if ever, had had occasion to use recursion as developers. One even felt that it was a code smell.
Most of you know that these days I’m mostly interested in Lisp and that I’ve put in a bunch of time with Scheme. It’s no surprise, therefore, that recursion is one of the main tools in my kit. But before I ever wrote a single line of Lisp I was still a recursion user. I can’t tell you how many depth-first searches I’ve written in C using recursion. Sure, if you’re writing accounting software you probably won’t find a good reason to use it but I’ve always found it an irreplaceable tool.
My problem is not with finding opportunities to use recursion but with forcing myself to consider seriously whether it’s the best solution for the problem at hand. Depth-first search? I don’t know how you can do it without recursion (simulating recursion with your own stack is just making a simple problem harder). A less clear cut example is the factorial function. I was trained as a mathematician so to me a natural way of thinking of the factorial is:
\begin{equation*} fact(n) = \begin{cases} n, &\text{if $n<3$;}\\ n × fact(n-1), &\text{otherwise.} \end{cases} \end{equation*}
That just screams for recursion, of course—the definition all but writes the code—but a loop may be a better solution in this case. The canonical example of that problem is the Fibonacci sequence:
\begin{equation*} fib(n)= \begin{cases} n, &\text{if $n<2$;}\\ fib(n-1)+fib(n-2), &\text{otherwise.} \end{cases} \end{equation*}
Again, this screams for recursion but disaster results if it’s implemented that way.
My point is that recursion itself is natural for anyone with even a minimal mathematical background. The real problem is knowing when it’s a good idea and when it’s not. Once you’ve got that under control, you can start considering things like tail recursion.
As to the larger point, I’m interested in how many of you use recursion without thinking of it as a special event. Leave a comment if you’d like to share your experience.