I'd like to second the above recomendation. HOP is a magnificent book.

The rest of Dominus' site has some really good resources (not necessarily about recursion) as well.

some functional programming links:

• IBM Developer Works
• Perl Design Patterns on Functional Programming
• MJD's fp class slides


TGI says moo

I think your problem is in your assumption of the maximum possible value for the square root of numbers in the range of 0 to 1.

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

# Tests

sub test
{
    my $n = shift;
    print "SQRT $n: ", &sqrt( $n ), ' ?= ', eval { CORE::sqrt( $n ) } 
+, $/, $/;
}

test( $_ ) for( 16, 9, 4, 2, 0.5, -1, 0, 0.001 );
[download]

SQRT 16: 4.0000114440918 ?= 4

SQRT 9: 3 ?= 3

SQRT 4: 1.99998474121094 ?= 2

SQRT 2: 1.4141845703125 ?= 1.4142135623731

SQRT 0.5: 0.7071533203125 ?= 0.707106781186548

SQRT -1:  ?= 

SQRT 0: 0.0078125 ?= 0

SQRT 0.001: 0.03125 ?= 0.0316227766016838
[download]

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

Don't pass parameters like that, it's confusing: which shift gets executed first? I'd either use it if only one is involved at a time, and possibly if I have to use the rest of @_ as a whole, or stick with:

my ($n,$m)=@_;
[download]

(I tend not to use $a and $b as general purpose variables even when they wouldn't be error prone because... their use is potentially error prone.)

It's a commonly recommended style to put a semicolon on the last line too.

Oh, and there's no need to use prototypes. Actually many people deprecate them. I find them useful for code and autorefs, but other than that they don't buy you much.

print "SQRT 16:\n",  &sqrt( 16 ), $/, $/;
[download]

&-form of sub call is now obsolete and most likely not to do what you want. Read more about this in perldoc perlsub.

If I were writing the middle subroutine, I wouldn't copy the values into other variables before use:

sub middle {
    return ($_[0] + $_[1]) / 2;
}
[download]

But that's probably just me.

duff

Indeed: YAWTDI!

Oh, and there's no need to use prototypes. Actually many people deprecate them.

The OP's code even does what you've said "many people" do. Using the & prefix to call a sub disables prototype checking. The combination of both &sub and prototypes should be a red flag (in addition to each being a red flag in and of themselves).

The OP's code even does what you've said "many people" do. Using the & prefix to call a sub disables prototype checking. The combination of both &sub and prototypes should be a red flag (in addition to each being a red flag in and of themselves).

I second that thoroughly. And it was very good of you to underline this sort of "synergy", because I didn't. Actually since there are prototypes, this may be one situation in which &sub may have sense, to overcome them. But it does not have sense to overcome them, so just as in the vast majority of cases, it's not needed and better avoided, period.

If I needed to pull more than one value off the front of @_ and leave the rest I'd possibly use splice:

my ($arg1, $arg2) = splice 0, 2, @_;
[download]

but more likely I'd pull the tail elements out into an array:

my ($arg1, $arg2, @tail) = @_;
[download]

---

DWIM is Perl's answer to Gödel

Well, I do use splice occasionally, but not for argument passing. I'd either do

my $arg1=shift;
my $arg2=shift;
[download]

or as in your second alternative, the point still being that multiple shift's on one line can be confusing albeit potentially correct, and IMHO clearly neither particularly concise nor expressive in terms of readability. Anyway what I choose depends on the emphasis I want to put on each argument. Fortunately in a not (any more) so remote future we will avoid all these parameter passing acrobatics...

And remember that $a and $b are the special comparison variables for sort(). It's a bad habit to use meaningless variable names anyway - let's move on past FORTRAN!

I'd recommend maybe

sub middle {
  my($low, $high) = @_;
  return ($low + $high) / 2;
}
[download]

because it's now much more evident that the "middle" is the value between low and high.

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.

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:

Incidentally, one can fine a thorough discussion of these matters, and one likely to be particularly suited for the OP's (and everyone else's) learning purposes, in chapter 13 of the book that one of our monks is writing.

UPDATE: Gah! Immediately upon pressing the "create" button, I realized it was totally wrong. Please ignore this post...

UPDATE 2: L~R pointed out that removing the node contents isn't cricket. So I'm sticking in my original comment (as best as I can remember it). The only thing I can say in my defense is that I was embarrassed by such a boneheaded mistake. Ah, well, heavy coding in C++ for a few weeks certainly warps your perception of syntax. ;^)

--roboticus

Nothing is totally wrong :)

The only thing that you did not consider is that x*x < x for x < 1. That's why your code doesn't work for input < 1.

Apart from that a couple of small comments concerning your code.

• Don't use prototypes for your subroutines unless you know exactly what you are doing.
• Don't use the variables $a and $b, they are special and used for sort.
• Instead of writing my ($x, $y, $z) = (shift, shift, shift); simply write my ($x, $y, $z) = @_;.

-- Hofmator

Code written by Hofmator and posted on PerlMonks is public domain. It is provided as is with no warranties, express or implied, of any kind. Posted code may not have been tested. Use of posted code is at your own risk.

roboticus,
Removing a node's content is generally frowned upon regardless of correctness. It is best to strike what is wrong or add an update then to remove it entirely. People do learn from other's mistakes.

FWIW, here is my take without having looked any other solutions to include monsieur_champs'.

print sqrt($_), "\t", mysqrt($_, .0000001), "\n" for qw/.25 .50 .75 1 
+10 50 100 1000 31415926/;
sub mysqrt {
    my ($tgt, $err, $try, $len) = @_;
    return 1 if $tgt == 1;
    if (! defined $try) {
        ($len, $try) = $tgt < 1
            ? ((1 - $tgt) / 2, $tgt + (1 - $tgt) / 2)
            : ($tgt / 2, $tgt / 2);
        return mysqrt($tgt, $err, $try, $len);
    }
    my $dif = $tgt - ($try * $try);
    return $try if abs($dif) < $err;
    $len /= 2;
    $try = $dif > 0 ? $try + $len : $try - $len;
    return mysqrt($tgt, $err, $try, $len);
}
[download]

If it isn't obvious, it is a binary search.

Update: The adjustment for values < 1 can be mathematically simplified. Additionally, a much faster converging algorithm would be $try = (($tgt / $try) + $try) / 2.

Cheers - L~R

Right, but his point was that he wanted to try something, which is an attitude to be encouraged. Maybe it's not effective, or better, or useful, but it's exploring to find out how to do something in a different way, and understanding how to use the tools to do it.

If you're comfortable with thinking about a problem in multiple ways, you can learn when to use one versus another. If you only know how to do iterative solutions, recursive ones look strange and challenging (or vice versa, for those whose first language was LISP).