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

... 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...

If a nested subroutine refers to variables from an enclosing sub, it needs a pointer to the enclosing sub's stack frame. This means that the compiler is passing around an extra parameter that you don't see. No free lunch here.

We neither have to pass a reference into the sub to hold our results, nor ...

Correction: You don't have to pass a reference into the sub explicitly. Perl does it for you automatically. The mechanism for that might be a bit more efficient than using ordinary references, but that's not necessarily true beyond the current incarnation of Perl.