Perl: the Markov chain saw PerlMonks

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

by Aristotle (Chancellor)
 on Dec 18, 2004 at 02:15 UTC ( #415817=note: print w/replies, xml ) Need Help??

in reply to Re: 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;
}

And for that matter, an iterative form:

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

Makeshifts last the longest.

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

There's a bug in that code, try finding the max of this list...
```@a = (1,0,3,2);

-- All code is 100% tested and functional unless otherwise noted.
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;
}

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.

Create A New User
Node Status?
node history
Node Type: note [id://415817]
help
Chatterbox?
 [vrk]: Hope he gets better soon. [Discipulus]: hdb sorry i profit; is known that a prime number is never a figurate one nor the sumattion of two adjacent figurates of the same order? like 3th triangular+3th tetrahedric [Discipulus]: if known where i can read about the matter? [choroba]: he's not really sick, we just got nobody to look after him today [Discipulus]: create an account for him; we are funny baby sitters ;=) come here child, want to listen the typeglob tale? [vrk]: choroba Oh, that's good. [vrk]: Discipulus I don't know much about prime numbers, but wouldn't that kind of an answer be in a graduate-level number theory book? [Discipulus]: my 8 yo daughter has two weeks of sleep disturbs.. we are gonna be crazy..

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (9)
As of 2017-04-27 07:57 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
I'm a fool:

Results (501 votes). Check out past polls.