Dear Monks

I'm training to implement recursive functions based on iteractive processes. For this, I decided to implement a binary search function to finding square roots of numbers without using loops. This is a personal study project, not a school task of any form.

At this moment, I already have a fair good implementation that fit my study needs. I'm not looking for the best solution for the problem of finding square roots. Isaac Newton toke care of this many years ago. ;-) I'm trying to learn better recursive programming techniques.

But I'm facing a funny problem here: I'm not sure how to make the search converge for numbers greather than zero and smaller than 1. Maybe someone here could give me a hand suggesting a method for handling those cases, without using loop keywords.

Thanks in advance for your help. Code follows.

#!/usr/bin/perl
use strict;
use warnings;

sub middle ($$) {
  my ( $a, $b ) = ( shift, shift );
  return ($a + $b) / 2
}

sub square ($) {
  my $x = shift;
  return $x**2;
}

sub abs ($) {
  my $n = shift;
  return $n < 0 ? -$n : $n;
}

sub sqrt_search{
  my ( $x, $base, $top, $guess, $counter ) = ( shift, shift, shift, sh
+ift, shift );
  print "sqrt-search( $x, $base, $top, $guess )\n";
  return $guess if( abs($x - square $guess) < 0.0001);
  return undef if $counter == 0;
  return sqrt_search( $x, $guess, $top, middle( $guess, $top ), --$cou
+nter)
    if( ($x > 0) and (square $guess < $x) );
  return sqrt_search( $x, $base, $guess, middle( $base, $guess ), --$c
+ounter)
    if( ($x > 0) and (square $guess > $x) );
  return undef;
}

sub sqrt ($) {
  my $x = shift;
  return sqrt_search( $x, 0, $x, middle(0, $x), 50);
}

# Tests
print "SQRT 16:\n",  &sqrt( 16 ), $/, $/;
print "SQRT 4:\n",   &sqrt( 4  ), $/, $/;
print "SQRT 2:\n",   &sqrt( 2  ), $/, $/;
print "SQRT 0.5:\n", &sqrt( .5 ), $/, $/;
print "SQRT -1:\n",  &sqrt( -1 ), $/, $/;
print "SQRT 0:\n",   &sqrt( 0  ), $/, $/;
[download]