in reply to
Re: Behold! The power of recursion.
in thread Behold! The power of recursion.
It is worth noting that while an iterative solution will almost inevitably run faster than a recursive solution, a good recursive solution is often quite terse.
It's further worth noting that DigitalKitty's algorithm uses only simple tail recursion, which can be easily compiled to be as fast or faster than an iterative solution.
Although I'm no expert, I believe the compiler would actually have to be smarter to optimize your iterative solution compared to the tail recursive one. Making the inference that $lower and $higher are candidates for register variables is slightly easier to make in the tail recursive version as there is a tendency to use registers for the subroutine calls variables for low-arity functions.
I could be wrong there, but a good compiler could do about as well with either, I would bet.
Now, implementing full tail call elimination is trickier, but recognizing tail recursion in this case and performing the optimization is a fairly trivial thing to do. Of course, we are talking about perl code here, and perl does not perform this optimization...