Recursion can often lead to elegant and short solutions (one of the reasons I like it so much), but it can, most definitely, be misused.
Learning recursion in school
I think just about every computer science course I've ever taken that (even remotely) mentions recursion, uses either factorial or Fibonacci as the starter sample to help students gets their heads around the concept. This is okay (I guess) as long as it's made clear that recursion is not the optimal solution for either of these.
It was in fact made clear to me in school that recursion is not ideal for factorial and Fibonacci, but for some reason that didn't stop me from using a recursive factorial function once.
This, it turned out, was not just a bad decision; it was a horrible decision.
Idiot me
I'm not proud of it, and I'm still not entirely sure what possessed me to do it (especially knowing full-well that the iterative solution is better). Maybe it was my love of short, simple, readable code, or maybe my brain was just malfunctioning that day (but I tend towards the former; it's gotten me into trouble before).
In fact, if I remember correctly, the exact thought that went through my head that day went something like this:
You know... I remember learning that a factorial function should never be written recursively (except perhaps as a teaching example) because the iterative solution is much more efficient. But if I use recursion just this one time, I can get this nifty, one-line factorial function, and it looks just oh so pretty! Plus, I won't be using this function very often at all, so I don't think it will matter much.
Boy did that (horrible) rationalization miss the mark! It did matter, it mattered a lot. And to make the situation worse, I did end up using the function often (very very very often, and that might be an understatement).
Why so many factorials?
Our profiling tool indicated that the factorial function was being invoked over a million times! Whoa, now that's not good. Did I mention this was all in Javascript? Yeah, it was, so it's even worse.
So why all the factorials? Well, I was doing some fairly complex math involving Bezier curves. Part of that math involves Binomial coefficients which is defined as:
n! / (k! * (n-k)!)The net effect of this was (roughly) a 7 second delay in the PLT of the particular page in which this script was running. Again, not good.
Lesson learned
So, as quickly as I could, I removed that dreadful (but pretty) one-line, recursive factorial function (hoping no one would notice) and replaced it with an iterative one. This boosted performance tremendously -- only took about 400ms to perform the same calculation.
Feeling so guilty for having made the poor decision to use recursion in the first place though, I still wasn't happy with my 400ms solution. I decided to see what else I could do to improve the performance. Turns out I was able to do some pre-computation and get the entire time down to about 48ms!
Ah, now I feel redeemed.
Heed this warning
So let this be a lesson to you: Use recursion wisely, only when appropriate, and in the case of Javascript, almost never!
Comments welcome.