finding maximum element in an array recursively


F

Feyruz

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

Advertisements

L

Lars Madsen

Feyruz said:
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
 
F

Feyruz

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.
 
A

Anno Siegel

Feyruz said:
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
 
F

Feyruz

Hi Anno Siegel,
The question comes from a book. I wanted to see if someone had better
or more creative solutions than I. I see that you are absolutely good
in it. So that causes the run-time to fall to O(log n). i find this
impressive
Thanks for your interesting solution.
F.
 
F

Feyruz

Wait a second, each half takes also O(n) doesnt it? i mean , are you
sure that it has any advantages?
 
Ad

Advertisements

F

Feyruz

Hi Perl Gurl,
The sub is supposed to recieve only integer values. I dont understand
why you run tests on it using letters.
F.
 
X

xhoster

Feyruz said:
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.

If the recursion is done well (Like Anno's, unlike in your original post)
it will use a recursive call depth of only lg N. It does store a lot of
data on the recursion stack, but again if done well it only uses about N
space (1/2N + 1/4N + 1/8N ...), whereas yours uses N**2 space on the stack.
You could make it use lg N space by passing index ranges, rather than
copies of the actual array portions, around the recursive sub, but that
would require to have a 2nd wrapper to allow you to call it naturally.
To: Lars Madsen

You asked me why i wanted a recursive function. As i wrote in the
beginning, it is for educational purposes.

While you can learn stuff using toy problems, I think educational purposes
are better served by learning not to do stupid things, rather than learning
how to do stupid things well. There are plenty of problems that actually
benefit from recursion, so there is no reason to force recursion onto
problems that don't benefit from it.

Xho
 
X

xhoster

Feyruz said:
Wait a second, each half takes also O(n) doesnt it? i mean , are you
sure that it has any advantages?

Over what? Over your method? Certainly. While it makes twice as many
recursive calls as your method, it uses 460 times less memory (for N=10,
000).

Over not doing it recursively in the first place? No, no advantages.

Xho
 
E

Eden Cardim

Do not take that wrong;
it is not your code is broken but rather perl core's notion
of maximum numerical value for mixed array content, or
at least I think that is what is happening. It "appears"
perl core sorts and places negative numbers before
letters, for sorting order.

You're mistaken, the documentation for the built-in sort function says:
'If SUBNAME or BLOCK is omitted, "sort"s in standard string comparison
order.'
check perldoc perlfunc for more details
Run these arrays for interesting results. Maybe you better
know what causes differences in returns. I am guessing
perl core has difficulties determining numerical value
for some circumstances.

Wrong again, anno's max function compares two elements at a time in
numeric context. The problem is that the comparison will return the
right-most element if the values are equal, since 'z' is numerically
equivalent to 0, the value returned by max will depend on the position
of the elements in the $right and $left variables, $right will always
be returned when the values are equal. That means the code is broken,
and worse, I don't think it can be fixed because the code was meant to
be run on numbers.
Here are some tests for you to run:
@Array = qw (-10 -9 -8 -7 -6 0 -5 -4 -3 -2 -1 Z Y X W);
If you sort this, you'll get W because it's the rightmost greater
element in numeric context.
@Array = qw (Z Y X W -10 -9 -8 -7 -6 0 -5 -4 -3 -2 -1);
If you sort this, you'll get W because it's the rightmost greater
element in numeric context.

@Array = qw (-10 -9 -8 -7 -6 0 -5 -4 -3 -2 -1 W Y X Z);
Now you'll get Z
etc...
 
F

Feyruz

people, whats going on here. I just wanted to discuss an algorithm
here, i did not want anyone to come here and be arrogant because he or
she has more experience in programming language than others. I think
some people like to fight over the internet.
Purl Gurl, why dont you also behave more civilized before calling
others rude?

Anyway, thanks Lars, Anno and Xhos for your comments on my "stupid?"
(according to Xhos) problem.
F.
 
Ad

Advertisements

E

Eden Cardim

I am not interested in reading rudeness. Few readers are.
What I presented is to encourage discussion, not to provide
readers a chance to be rude.

Neither am I interested in writing rudeness, I'm interested in writing
facts, my apologies if they offend you. The discussion is supposed to
be technical (not personal), but eventually we all make mistakes. Due
to the lack of time, I didn't review my post as to not make it sound
rude.
Anno did not code for the type of data I exemplified, nor is he expected to do so.

Precisely what I mentioned before.
I have provided a reasonable "what if" situation which does not
reflect the quality of Anno's code; his code is very nice.

Thank you, by the way, I had quite some fun testing sort and re-reading
it's documentation.
 
A

A. Sinan Unur

people, whats going on here. I just wanted to discuss an algorithm
here, i did not want anyone to come here and be arrogant because he or
she has more experience in programming language than others. I think
some people like to fight over the internet.
Purl Gurl, why dont you also behave more civilized before calling
others rude?

Before you post in a newsgroup, you are expected to lurk for awhile. If
you had done that, or if you had looked at the archives, you would have
learned about PG's reputation.

In addition, it looks like you have not read the posting guidelines for
this newsgroup. Please do so, and please follow them. Your original post
followed all the guidelines, so that is a good thing. However, your
replies have omitted all context, and that is a bad thing.
Anyway, thanks Lars, Anno and Xhos for your comments on my "stupid?"
(according to Xhos) problem.
F.

Xho's diagnosis was spot on: It is stupid to find a maximum using
recursion. It should never be done, even as a learning tool. On the
other hand, neither his nor my comments are directed to you personally,
and you should not take them so.

Sinan
 
E

Eden Cardim

That is not quite true. The comparison will determine that the elements
being compared are equal. How the two elements end up in the final sort
order is determined by the "stability" of the sort. A sort which is
"stable" will retain the original order of equal elements. A sort which
is not stable is free to reorder equal elements.
<snip>

I don't think you noticed, but I'm talking about the max function
proposed earlier by Anno, not perl's sort builtin function. His code
obviously selects rightmost items if the items compared are equal:
$left > $right ? $left : $right
 
Ad

Advertisements

Ad

Advertisements


Top