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(...);
   }
}

[download]

including the trivial case 

sub func {
   ...
   return func(...);
}

[download]

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;
}

[download]

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);
}

[download]

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();
      }
   }
}

[download]

However, this makes the function much more complicated with little or no benefit.

In reply to Re: [Study]: Searching for square roots by ikegami
in thread [Study]: Searching for square roots by monsieur_champs

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • 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! —
  • 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:
    & &amp;
    < &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.