On Fri, Apr 05, 2013 at 09:03:13PM -0400, Conor Walsh wrote: > why is this that much faster than actual recursion? That speaks > poorly of lowercase-p perl.
This is not a perl specific issue (for the most part). Most languages that support function calls need to maintain an activation record for every call in order to keep track of, at the very least, parameters, return values, next action, etc [1]. A recursive function creates a chain of these records. So, Uri's suggestion is faster because replacing recursion with iteration and stack operations uses fewer resources than the runtime does in maintaining a call stack. More to the point though, one avoids the built in limits, or rather, exchanges that limit for memory limits. I don't think this speaks poorly of perl at all. Every operation has a cost, after all, and function calls are relatively expensive. Certainly more so than iteration or array operations. [1] There are a couple of ways to avoid this problem while still maintaining the benefits of recursion. One is to use threaded code, as in Forth, or more commonly, to use tail recursion (or tail call elimination), which re-uses the current activation record for the recursive call, iff the recursive call occurs at the end of the function since that means that the only state we need store are the return values. Since those are on the stack, they can, with a bit of pointer twiddling or copying, become the parameters to the next call. A number of languages do this, to great advantage. Perl does not have tail call elimination. However, it is mentioned in "Porting/todo.pod" -Gyepi _______________________________________________ Boston-pm mailing list [email protected] http://mail.pm.org/mailman/listinfo/boston-pm
