A very important skill in writting recursive functions is knowing how to get rid of trivial recursion.
Functions of the form
sub func {
...
if (...) {
...
return ...;
} elsif (...) {
...
return ...;
} elsif (...) {
...
return func(...);
} elsif (...) {
...
return func(...);
}
}
including the trivial case
sub func {
...
return func(...);
}
can be made non-recursive trivially. They are said to be "tail recursive". Your function is tail recursive, so it can be optimized. After removing tail recursion, your code looks like the following:
use constant SQRT_EPSILON => 0.0001;
use constant SQRT_MAX_ITER => 50;
sub sqrt ($) {
my $x = shift;
return undef if $x < 0;
my $base = 0;
my $top = $x;
my $guess = middle($base, $top);
my $counter = SQRT_MAX_ITER;
while (abs($x - square $guess) >= SQRT_EPSILON) {
# Avoid looping for too long.
return undef unless $counter--;
if ( square $guess < $x ) {
$base = $guess;
$guess = middle( $guess, $top );
}
elsif ( square $guess > $x ) {
$top = $guess;
$guess = middle( $base, $guess );
}
}
return $guess;
}
Update:
Any loop can be converted into a recursive solution, but not all recursive solutions can be made into a (simple) loop. A recursive algorithm that doesn't use tail recursion is a depth-first visit of a tree.
sub in_order_visit {
my ($node, $visitor) = @_;
return unless defined $node;
in_order_visit($node->left(), $visitor);
$visitor->($node);
in_order_visit($node->right(), $visitor);
}
Recursion can still be eliminated by replacing the call stack with a local stack.
sub in_order_visit {
my ($node, $visitor) = @_;
my @to_process;
for (;;) {
if (defined $node) {
push(@to_process, $node);
$node = $node->left();
} else {
return if not @to_process;
$node = pop(@to_process);
$visitor->($node);
$node = $node->right();
}
}
}
However, this makes the function much more complicated with little or no benefit.
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.