go ahead... be a heretic PerlMonks

### Removeing Unecessary Recursion

by ikegami (Pope)
 on Oct 18, 2004 at 04:49 UTC ( #400060=note: print w/replies, xml ) Need Help??

in reply to Behold! The power of recursion.

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);
}

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;
}
}
}

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!

Replies are listed 'Best First'.
Re: Removeing Unecessary Recursion
by jordanh (Chaplain) on Oct 18, 2004 at 15:59 UTC
Uhh... DigitalKitty's solution was already tail recursive.

Create A New User
Node Status?
node history
Node Type: note [id://400060]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (3)
As of 2017-08-17 08:44 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Who is your favorite scientist and why?

Results (285 votes). Check out past polls.

Notices?