Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
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.

Log In?
Username:
Password:

What's my password?
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 having an uproarious good time at the Monastery: (6)
As of 2017-11-23 03:03 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    In order to be able to say "I know Perl", you must have:













    Results (328 votes). Check out past polls.

    Notices?