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

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.