finding maximum element in an array recursively
in [Perl]
|
From: Feyruz on 30 Nov 2005 09:40 hello, can someone show me other ways to find the max. element in an array recursively? Other than shown in the code below? (for educational purposes). I can imagine that it is not the best way because of memory usage. use strict; use warnings; #Author: Feyruz Yalcin/Groningen/Netherlands #Algorithmica Exerc. R-4.7. P.179 sub max { my @ar = @_ if ( @_ ); if ( $#ar==0 ) { return $ar[0]; } else { my $max = pop( @ar ); my $other = max( @ar ); if ( $max > $other ) { return $max; } else { return $other; } } } #example run my @price = (10, 10, 6, 3, 4, 2, 5, 7, 132, 3, 10, 6, 3, 4, 2, 10, 6, 3, 4, 2, 5, 7, 5, 7, 4, 2, 5,6, 3, 4, 2, 10, 6, 3, 4, 2, 5, 7, 5, 7, 4, 2, 5,7); print max(@price);
From: Lars Madsen on 30 Nov 2005 09:54 Feyruz wrote: > hello, > can someone show me other ways to find the max. element in an array > recursively? Other than shown in the code below? (for educational > purposes). I can imagine that it is not the best way because of memory > usage. > > use strict; > use warnings; > > #Author: Feyruz Yalcin/Groningen/Netherlands > #Algorithmica Exerc. R-4.7. P.179 > > > sub max { > my @ar = @_ if ( @_ ); > if ( $#ar==0 ) { > return $ar[0]; > } else { > my $max = pop( @ar ); > my $other = max( @ar ); > if ( $max > $other ) { > return $max; > } else { > return $other; > } > } > > } > #example run > my @price = (10, 10, 6, 3, 4, 2, 5, 7, 132, 3, 10, 6, 3, 4, 2, 10, 6, > 3, 4, 2, 5, 7, 5, 7, 4, 2, 5,6, 3, 4, 2, 10, 6, 3, 4, 2, 5, 7, 5, 7, 4, > 2, 5,7); > print max(@price); > why recursively? sub max { my @ar = @_ ; return undef unless @ar; # or similar my $max = shift @ar; # start value for my $p (@ar) { if ($p > $max) { $max=$p; } } return $max; } untested (i'm sure there are even better ways even modules for doing this) /daleif
From: Purl Gurl on 30 Nov 2005 10:50 Feyruz wrote: > can someone show me other ways to find the max. element in an array > recursively? Other than shown in the code below? My presumption is your "max. element" means the array element with the maximum numerical value. Usually your "max. element" would mean the scalar (@Array) value or the $#Array value, depending on context. Perl's sort function is a default recursive function. It is important to be sure your array contents will not cause problems; there are circumstances under which sort will fail. Research and read about sort to learn of various syntax used. Purl Gurl #!perl @Array = qw (-11 9 -8 7 -6 5 -4 3 -2 1 0 d 10 c b a); @Array = sort {$a <=> $b} @Array; print "Maximum Number: $Array[-1]"; print "\n"; @Array = qw (-10 -9 -8 -7 -6 0 -5 -4 -3 -2 -1); @Array = sort {$a <=> $b} @Array; print "Maximum Number: $Array[-1]"; print "\n"; @Array = qw (-10 -9 -8 -7 -6 0 -5 -4 -3 -2 -1 Z Y X W); @Array = sort {$a <=> $b} @Array; print "Maximum Number: $Array[-1]";
From: Feyruz on 30 Nov 2005 11:01 To: Perl Guru So you say that Perl also uses a recursive function to find the element with the maximum numerical value in an array ? I find this interesting. Because i was thinking that a recursive function would use up a lot of memory when it deals with large arrays if it is used for this kind of work. To: Lars Madsen You asked me why i wanted a recursive function. As i wrote in the beginning, it is for educational purposes. So the results that you supplied look okay, but i had not asked it for the results that you gave but rather for the way you can solve the problem. Thanks anyway, F.
From: Anno Siegel on 30 Nov 2005 11:05
Feyruz <feyruzyalcin(a)hotmail.com> wrote in comp.lang.perl.misc: > hello, > can someone show me other ways to find the max. element in an array > recursively? Other than shown in the code below? (for educational > purposes). I can imagine that it is not the best way because of memory > usage. > > use strict; > use warnings; > > #Author: Feyruz Yalcin/Groningen/Netherlands > #Algorithmica Exerc. R-4.7. P.179 > > > sub max { > my @ar = @_ if ( @_ ); > if ( $#ar==0 ) { > return $ar[0]; > } else { > my $max = pop( @ar ); > my $other = max( @ar ); > if ( $max > $other ) { > return $max; > } else { > return $other; > } > } > > } > #example run > my @price = (10, 10, 6, 3, 4, 2, 5, 7, 132, 3, 10, 6, 3, 4, 2, 10, 6, > 3, 4, 2, 5, 7, 5, 7, 4, 2, 5,6, 3, 4, 2, 10, 6, 3, 4, 2, 5, 7, 5, 7, 4, > 2, 5,7); > print max(@price); One wonders why maximum extraction would be implemented recursively, recursion offers absolutely no advantage here. If it has to be, I wouldn't split off one element per step but split the list in even halves. That way, for n elements, you get log n recursive calls instead of n. sub max { die "can't take max of no elements" unless @_; if ( @_ == 1 ) { return shift; } else { my $left = max( @_[ 0 .. @_/2 -1]); my $right = max( @_[ @_/2 .. $#_]); return $left > $right ? $left : $right; } } Anno -- If you want to post a followup via groups.google.com, don't use the broken "Reply" link at the bottom of the article. Click on "show options" at the top of the article, then click on the "Reply" at the bottom of the article headers. |