Re^2: Finding the max()/min()

Here's another recursive form:

sub max {
    my( $i, @l ) = @_;
    my $j = @l ? max( @l ) : $i;
    return $i > $j ? $i : $j;
}
[download]

And for that matter, an iterative form:

sub max {
    $_[ 0 ] < $_[ -1 ] ? shift : pop while @_ > 1;
    return @_;
}
[download]

Makeshifts last the longest.

Comment on Re^2: Finding the max()/min() Select or Download Code

Replies are listed 'Best First'.
Re^3: Finding the max()/min() by elusion (Curate) on Dec 18, 2004 at 17:26 UTC
It's normally best to end recursive solutions with the recursive call. That allows the compiler to use tail-recursion to speed up the solution. Of course, in Perl you need to jump through a few hoops to do use tail-recursion, so I mentioned but didn't include it in my original node. But with a bit if tinkering you can use it, and here it is now: `sub max { my $max = shift; my $next = shift; return $max if not $next; unshift @_, $max > $next ? $max : $next; goto &max; }` [download] Which I estimate to be about 10x faster on a random 5000 element list. (Exact benchmarks are left to the reader as an exercise :-). I wonder if Ponie (Perl 5 On New Internals Engine) will be able to detect and use tail-recursion. elusion : http://matt.diephouse.com	[reply] [d/l]
Re^4: Finding the max()/min() by sleepingsquirrel (Chaplain) on Dec 19, 2004 at 01:40 UTC
There's a bug in that code, try finding the max of this list... `@a = (1,0,3,2);` [download] -- All code is 100% tested and functional unless otherwise noted.	[reply] [d/l]
Re^5: Finding the max()/min() by elusion (Curate) on Dec 19, 2004 at 02:21 UTC
Good catch; I forgot the edge case. Here's the fix: `sub max { my $max = shift; return $max if not @_; my $next = shift; unshift @_, $max > $next ? $max : $next; goto &max; }` [download] elusion : http://matt.diephouse.com	[reply] [d/l]
Re^4: Finding the max()/min() by Aristotle (Chancellor) on Dec 19, 2004 at 05:45 UTC
That's all well and nice, but my goal was to use an approach which directly generalizes from the specific case of a two element list. As you'll also notice I used the value returned from the recursive call twice, it's both kind of difficult and beside the point to work on tail recursion here. Noone in their right mind writes a recursive max() outside a functional language anyway, and in a pure functional language I'd just write `max( @l )` twice and let the compiler/VM figure out that the result need only be calculated once. In any case, your new approach is just a variation on what was already posted in the parent node — no need for repetition… Makeshifts last the longest.	[reply] [d/l]