Recursion is slow because all the arguments must be pushed onto the stack (in the case of Perl, the @_ variable). By eliminating any arguments passed in a recursive algorithm, you eliminate the speed problem, since nothing needs to be pushed onto the stack.

The example above probably isn't the best example of this, since $iGlobal still needs to be shifted off the stack.

----
Reinvent a rounder wheel.

Note: All code is untested, unless otherwise stated

That only works if you don't have much state to remember. Recursion starts getting fun when there's significant state, for instance, when you are doing divide-and-conquer, a very common technique to solve problems. (Basically, it means: divide the data set into 2 or more smaller sets. Solve the problem for the smaller sets, then combine the answers). Sorting can be done that way (quicksort, mergesort), enumerating range queries on trees typically work this way, building convex hulls, etc, etc.

You can of course use iterative versions of the recursive algoritms. But you'll notice that for any non-trivial algorithm, you'll need a stack to remember your state.

Abigail

By eliminating any arguments passed in a recursive algorithm, you eliminate the speed problem, since nothing needs to be pushed onto the stack.

• That doesn't eliminate the recursion, it only eliminates the parameter passing.
• Only in trivial recursions can you eliminate the need to push variables on the stack.
• You still have to push the return address onto the stack, anyway.

I think the idea the OP was trying to touch on was that you can reduce the size and time of the stack by using some kind of "global" variable instead of passing everything by parameter. Pascal had a mechanism for this (nested subroutines) that C lacks, and that Perl more or less lacks. (Yes believe it or not there are one or two cooler features in Pascal than in C/Perl. ;-) This is also nice because with recursive routines you often want to have a "wrapper" sub that sets up the recursion (perhaps does argument checking and the other initialization) that then calls the "real" recursive sub. Since Perl doesnt have "real" nested subs (Broquaints efforts aside :-) you need to do it like this:

sub inorder {
  my ($root)=@_;
  my $code;
  my @inorder;
  $code=sub {
             my $node=shift;
             $code->($node->left) if $node->left;
             push @inorder,$node->value;
             $code->($node->right) if $node->right;
            };
  $code->($root);
  return \@inorder;
}
[download]

Admittedly this example is so simple it probably doesnt deserve the extra treatment, but you can see my point in that it mimizes the amount of usage of the stack. We neither have to pass a reference into the sub to hold our results, nor utilize the much less efficient means of returning larger and larger lists to the calling sub. I've done a number of benchmarks using this approach with much less trivial recursion that this and the benefits were non-negligble. I also like it because it means that noone "accidentally" calls a sub intended for recursion that does not do argument checking on the pretense that the wrapper handles it already.

Dont get me wrong though, I agree that there is usually more benefit in writing an iterative solution than this approach (just having to _really_ think the problem through results in unforseen optimizations in my experience). The real question is whether its worth the effort when a reasonable middle ground is available. :-)

---
demerphq