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.