It is something of an axiom that any recursive solution can be rewritten as an iterative one. Often a finite infinite loop is useful:

#!/usr/bin/perl -w

use constant HIGH => 10_000;
my $ans = int(rand(HIGH)) + 1;
my ( $lower, $higher ) = (1, HIGH);
while(1) {
    my $guess = int(($lower + $higher)/2);
    print "Guessing: $guess\n";
  last if $ans == $guess;
    if ( $guess > $ans ) {
        print "Lower...";
        $higher = $guess -1;
    }
    else {
        print "Higher...";
        $lower = $guess +1;
    }
}
print "The guess was correct!";
[download]

FWIW, with your code &function(args) syntax is not considered best style, you can drop the & - which you actually do in the sub. A consistent style is a good idea. You could declare and set $ans in one call.

It is worth noting that while an iterative solution will almost inevitably run faster than a recursive solution, a good recursive solution is often quite terse. A classic very simple example is the calculation of factorial n! The factorial is defined n! = 1 x 2 x 3 x .... (n-1) x n You can code using either iteration or recursion.....

sub fact_rec{ 
    my ($num) = @_;
    $num ? $num*fact_rec($num-1) : 1 
}

sub fact_it{
    my ($num) = @_;
    my $fac = 1;
    for my $i( 1 .. $num ) {
        $fac *= $i;
    }
  return $fac;
}

for (1..10){
    printf"%d!\t%10d\t%10d\n", $_, fact_rec($_), fact_it($_);
}
[download]

As you can see the recursive solution is short and sweet. It also has a bug that can cause it to go infinite. One gotcha with recursion is that you need to be *positive* that your exit condition (ie stop recursing when we are done) will be *always* be met. A typical real world use for recursion is in dealing with tree like structures

The bug:

Negative numbers or floats mean that $num -1 will never equal 0, and so always it will always be true.

It is worth noting that while an iterative solution will almost inevitably run faster than a recursive solution, a good recursive solution is often quite terse.

It's further worth noting that DigitalKitty's algorithm uses only simple tail recursion, which can be easily compiled to be as fast or faster than an iterative solution.

Although I'm no expert, I believe the compiler would actually have to be smarter to optimize your iterative solution compared to the tail recursive one. Making the inference that $lower and $higher are candidates for register variables is slightly easier to make in the tail recursive version as there is a tendency to use registers for the subroutine calls variables for low-arity functions.

I could be wrong there, but a good compiler could do about as well with either, I would bet.

Now, implementing full tail call elimination is trickier, but recognizing tail recursion in this case and performing the optimization is a fairly trivial thing to do. Of course, we are talking about perl code here, and perl does not perform this optimization...

I believe

Benchmark knows.

Benchmark: timing 1000000 iterations of iterative_c, iterative_p, recu
+rsive_c, recursive_p...
iterative_c:  1 wallclock secs ( 1.10 usr +  0.00 sys =  1.10 CPU) @ 9
+07441.02/s (n=1000000)
iterative_p: 19 wallclock secs (19.52 usr +  0.00 sys = 19.52 CPU) @ 5
+1234.76/s (n=1000000)
recursive_c:  1 wallclock secs ( 1.16 usr +  0.00 sys =  1.16 CPU) @ 8
+60585.20/s (n=1000000)
recursive_p: 36 wallclock secs (36.26 usr +  0.00 sys = 36.26 CPU) @ 2
+7576.32/s (n=1000000)
                Rate recursive_p iterative_p recursive_c iterative_c
recursive_p  27576/s          --        -46%        -97%        -97%
iterative_p  51235/s         86%          --        -94%        -94%
recursive_c 860585/s       3021%       1580%          --         -5%
iterative_c 907441/s       3191%       1671%          5%          --
[download]

Read more... (2 kB)

"It is worth noting that while an iterative solution will almost inevitably run faster than a recursive solution, a good recursive solution is often quite terse."

Fully agree. Although this demos recursion, it is not a good example to demo the NEED of recursion.

A typical situation where recursion becomes a clearer solution is that, you need complex stack data structure to remember things otherwise, which is not the case here.

"A classic very simple example is the calculation of factorial n!"

My favorite is Hanoi Tower problem.

I wanted to point out that your "guess the number" algorithm is O(log N) in its computational efficiency. What that means is that as the dataset (or in this case, the size of the range in which the secret number may be hidden) grows by "N", the amount of work needed to find the secret number grows by "log N".

This happens to be, roughly, the same algorithm used in a binary search, which is known to be O(log N) too (of course).

The recursion is mostly a convenience here. An iterative approach could be used to implement the same basic algorithm, but recursion is kinda cool. :)

By the way, Perl (with warnings turned on) warns you when your recursion level reaches 100 levels deep. You can turn this off, if I recall, with "no warnings qw/recursion/;".

"This happens to be, roughly, the same algorithm used in a binary search,"

Indeed this is binary search itself. This used to be a trick I played when I was a kid. I first ask other kids to have a number between 1 and 1024, don't tell me, just keep it to themselves. Then ask them whether they believe that I can guess their number by asking no more than 10 questions. Nobody believed me at the beginning, but ... ;-)

This is pretty easy to solve for "worst case" and "average case" mathematically. But DigitalKitty's script makes it pretty easy to also empirically test. This isn't intended to be a replacement for mathematical proof, but rather, just a quick real-world example of how efficient the binary-search algorithm is. For each of the items in the table below, a modified DigitalKitty script was run. The modification causes the script to search for random numbers ten times in each range, and then print the average number of guesses for those ten searches. In each case, the range is assumed to be "0 .. N".

So here are a few trial runs:

Range          Average Guesses
10             2.5
100            6
1000           9
10000          13
100000         16.5
1000000        19.5            (That's a range of 1 million)
1000000000     29.5            (That range is 1 billion)
1000000000000  39              (The range is 1 trillion)
[download]

So this unscientific example shows that you can find one number hidden among a range of one trillion numbers, on average, after 39 guesses, using a binary search. Also, it should be noted that the larger the range, the smaller the standard deviation in number of guesses needed, as a percent of total guesses. A binary search is fairly stable; not very sensitive to the dataset.

If you were to bet someone you could guess their number between zero and 100 in less than ten guesses, you will most likely walk home with the money. But you'll really surprise someone if you can guess a one out of a trillion number in well under 50 guesses.




Dave

Just to add something here, the log we use in computer science is log 2 not log 10. Hence log(10) is 2.30258509299405 not 1. Just in case anybody forgot this :-)



---
demerphq


First they ignore you, then they laugh at you, then they fight you, then you win.
-- Gandhi

Flux8

With slight changes, this can be made tail-recursive, which means the recursion can be elimited completely.

Tail-recursive variant:

sub cleverGuess {
   my( $lower, $higher ) = @_;

   my $guess = int(($lower + $higher)/2);
   print "Guessing: $guess\n";

   if ($guess == $ans) {
      print "The guess was correct!";
      return;
   }

   elsif ($ans < $guess) {
      print "Lower...";
      $higher = $guess-1;
   }

   else {
      print "Higher...";
      $lower = $guess + 1;
   }

   cleverGuess($lower, $higher);
}
[download]

Tail-recursion replaced with a loop:

sub cleverGuess {
   my( $lower, $higher ) = @_;

   for (;;) {
      my $guess = int(($lower + $higher)/2);
      print "Guessing: $guess\n";

      if ($guess == $ans) {
         print "The guess was correct!";
         return;
      }

      elsif ($ans < $guess) {
         print "Lower...";
         $higher = $guess-1;
      }

      else {
         print "Higher...";
         $lower = $guess + 1;
      }
   }
}
[download]

I don't mean to diminish your effort. I just wish to illustrate that power of recursion is sometimes an illusion. Performance should increase by removing recursion where it's not needed, and now you know how!

Uhh... DigitalKitty's solution was already tail recursive.

Just for fun, imagine those two functions are actually two guys talking: (Still recursion, but two functions involved, they call each other)

use strict;
use warnings;

use constant HIGH => 1024;

my $the_number = int(rand HIGH) + 1;
print "The number is $the_number\n";
my $high;
my $low;
my $answer;
my $guess;
ask_question();

sub ask_question {
    sleep(1);
    if (!$answer) {
        $high = HIGH;
        $low = 1;
    } elsif ($answer == 0) {
        return;
    } elsif ($answer == 1) {
        $low = $guess + 1;
    } elsif ($answer == -1) {
        $high = $guess - 1;
    }
    $guess = int(($low + $high) / 2);
    print "Is your number $guess? ";
    answer();
}

sub answer {
    if ($guess < $the_number) {
        print "Go higher ...\n";
        $answer = 1;
        ask_question();
    } elsif ($guess == $the_number) {
        print "You got it!\n";
        $answer = 0;
    } else {
        print "Go lower ...\n";
        $answer = -1;
        ask_question();
    }     
}
[download]

Result from one run:

The number is 1001
Is your number 512? Go higher ...
Is your number 768? Go higher ...
Is your number 896? Go higher ...
Is your number 960? Go higher ...
Is your number 992? Go higher ...
Is your number 1008? Go lower ...
Is your number 1000? Go higher ...
Is your number 1004? Go lower ...
Is your number 1002? Go lower ...
Is your number 1001? You got it!
[download]

This program tells how many guesses you need for a number range, including total number of guesses for all numbers in the range, and the average: (the basic idea behind it is that, you have 1 number that you can hit by exactly 1 guess, you have 2 numbers that you can hit by exactly 2 guesses, you have 4 numbers that you can hit by exactly 3 guesses... you have 2 ** n numbers that you can hit by exactly n + 1 guesses...)

use strict;
use warnings;

my $total;
for my $i (1 .. 20) {
    my $last = 2 ** $i - 1; 
    $total += $i * 2 ** ($i - 1);
    my $avg =$total / (2 ** $i - 1);
    print "For range 1 .. $last, total guesses = $total, avg = $avg\n"
+;
}
[download]

Output:

For range 1 .. 1, total guesses = 1, avg = 1
For range 1 .. 3, total guesses = 5, avg = 1.66666666666667
For range 1 .. 7, total guesses = 17, avg = 2.42857142857143
For range 1 .. 15, total guesses = 49, avg = 3.26666666666667
For range 1 .. 31, total guesses = 129, avg = 4.16129032258065
For range 1 .. 63, total guesses = 321, avg = 5.09523809523809
For range 1 .. 127, total guesses = 769, avg = 6.05511811023622
For range 1 .. 255, total guesses = 1793, avg = 7.03137254901961
For range 1 .. 511, total guesses = 4097, avg = 8.01761252446184
For range 1 .. 1023, total guesses = 9217, avg = 9.00977517106549
For range 1 .. 2047, total guesses = 20481, avg = 10.0053737176356
For range 1 .. 4095, total guesses = 45057, avg = 11.0029304029304
For range 1 .. 8191, total guesses = 98305, avg = 12.0015871078012
For range 1 .. 16383, total guesses = 212993, avg = 13.0008545443447
For range 1 .. 32767, total guesses = 458753, avg = 14.0004577776421
For range 1 .. 65535, total guesses = 983041, avg = 15.0002441443503
For range 1 .. 131071, total guesses = 2097153, avg = 16.0001297006966
For range 1 .. 262143, total guesses = 4456449, avg = 17.0000686648127
For range 1 .. 524287, total guesses = 9437185, avg = 18.0000362396931
For range 1 .. 1048575, total guesses = 19922945, avg = 19.00001907350
+45
[download]

++ to everyone who posted similar messages.

The only time that recursion is actually useful is when you're branching out.

I think you maybe have the "usefulness" of recursion confused with the "misuse of an un-optimized implementation of recursion in a language compiler".

Just because most C compilers inefficiently implement recursion and many other C based languages do not fix this problem does not mean it is a lost cause. If you look at the compiler technology underlying recent implementations of Standard ML, Haskell or Scheme you will see that recursion can be implemented efficiently.

-stvn

Would you please give URL references here. I would like to follow your thoughts, but am not familiar with the literature. This is a particularly interesting thread for me, having been severely reprimanded for using recursion (some years ago) and having made an effort to repress the impulse to use it ever since. -ben

You wanted suggestions and you have already recieved a good lecture on removal of tail recursion (as it should be done). I also recommend ditching the overly wordy java naming style, the calling convention, and adding "use strict".

sub g{my($b,$r)=@_;$s{$b}++||map{$p='.'x8x/[A-Z]/;$s||=$r x$b=~/$c
/||g($n=$b,"$r$c ".($n=~s/$_(($p$c)+$p)(?!$_)($c| )/$3$1$_/s-2*/ /).$/
+)for$",$c=$_}$b=~/\w/g;$s}$_=g$_
[download]