Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
Recursion Is Slow!
In the first year of a computer science degree program, you learn about two important things: induction and indirection—or, for the more practical, recursion and pointers. Once you've learned about recursion, you're quickly told that it's a nice theoretical model, but in practical code (in the real world), iteration is always faster: By all means, use a recursive algorithm for prototyping, but if you care about speed, then rewrite it as a loop.
Unlike the other examples we've examined so far, this advice isn't always wrong. I came across an example about a year ago, however, where it was very wrong. Someone had rewritten a nice recursive algorithm as a loop[el]and found that it ran noticeably slower. Because the programmer was using Visual Studio, my first instinct was to blame the compiler, which wasn't entirely fair; I've only come across one instance where the Microsoft C++ compiler has done anything really stupid. Anyway, I checked out the assembly for both versions. In both cases, it looked sensible. The iterative version did some clever rearrangement that made it quite difficult to follow—and made me very glad I rarely need to write assembly—but still, it ran slowly.
The reason turned out to be visible in the high-level code. This loop allocated an array as a local variable and then used it as a stack. The recursive version used the call stack directly. The iterative version needed to store a value by some offset from the stack pointer and then increment the offset. The recursive version could just use push-and-pop instructions, which happened very quickly as a single operation. Not surprisingly, the hardware stack was much faster than the one implemented entirely in software, and this speed difference was greater than the difference between the cost of the function call and the jump.
The moral of this story is that the most natural expression of an algorithm is likely to give you the fastest result. If your algorithm is naturally recursive, torturing it into a loop won't make it faster. If describing it as a loop makes sense, then making it recursive probably won't speed it up (or make it any slower, usually). A lot of compilers will now do tail-recursion optimization: If the last line in a function is a recursive call to the same function, the compiler will replace it with a jump to the start—exactly the same code you would get from a loop.