|Just another Perl shrine|
Re: Recursion Alternatives?by Arguile (Hermit)
|on Feb 27, 2003 at 06:14 UTC||Need Help??|
“Recursion is beautiful, but computers don't really grok beauty.”
Unfortunately this is true of Perl. While Perl 6 still holds some hope for tail-recursion optimisation, there’s no way to get the performance and elegance in Perl 5.
Tail recursion is signified by the recursive call being last executed statement. It can match iterative algorithms for speed and space usage as there is no unwinding phase needed, so the same stack frame can be used repeatedly instead of pushing another one on each call.
In your above code (repeated below) you used straight recursion.
Compare that to the same function rewritten in a tail recursive manner.
With an optimising compiler the tail recursive version would be comparable to an iterative approach in performance, while retaining it’s (arguable) elegance. This particular example doesn't look much easier or more elegant, but it can be.
As stated above though, Perl doesn’t optimise any form of recursion. So the best bet is to write it in some iterative fashion if you want performance.
(1) I didn’t bother trying to keep the fact() sub local for reasons of claity