in reply to Behold! The power of recursion.
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!";
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($_); }
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. |
cheers
tachyon
|
---|
Replies are listed 'Best First'. | |
---|---|
Re^2: Behold! The power of recursion.
by jordanh (Chaplain) on Oct 18, 2004 at 03:24 UTC | |
by tachyon (Chancellor) on Oct 18, 2004 at 04:10 UTC | |
by jordanh (Chaplain) on Oct 18, 2004 at 11:38 UTC | |
by tachyon (Chancellor) on Oct 18, 2004 at 22:19 UTC | |
by jordanh (Chaplain) on Oct 19, 2004 at 01:03 UTC | |
| |
Re^2: Behold! The power of recursion.
by pg (Canon) on Oct 18, 2004 at 03:16 UTC |