finding maximum element in an array recursively

Discussion in 'Perl Misc' started by Feyruz, Nov 30, 2005.

  1. Feyruz

    Feyruz Guest

    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);
     
    Feyruz, Nov 30, 2005
    #1
    1. Advertisements

  2. Feyruz

    Lars Madsen Guest

    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
     
    Lars Madsen, Nov 30, 2005
    #2
    1. Advertisements

  3. Feyruz

    Feyruz Guest

    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.
     
    Feyruz, Nov 30, 2005
    #3
  4. Feyruz

    Anno Siegel Guest

    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
     
    Anno Siegel, Nov 30, 2005
    #4
  5. Feyruz

    Feyruz Guest

    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.
     
    Feyruz, Nov 30, 2005
    #5
  6. Feyruz

    Feyruz Guest

    Wait a second, each half takes also O(n) doesnt it? i mean , are you
    sure that it has any advantages?
     
    Feyruz, Nov 30, 2005
    #6
  7. Feyruz

    Feyruz Guest

    Hi Perl Gurl,
    The sub is supposed to recieve only integer values. I dont understand
    why you run tests on it using letters.
    F.
     
    Feyruz, Nov 30, 2005
    #7
  8. Feyruz

    xhoster Guest

    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.
    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
     
    xhoster, Nov 30, 2005
    #8
  9. Feyruz

    xhoster Guest

    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
     
    xhoster, Nov 30, 2005
    #9
  10. Feyruz

    Eden Cardim Guest

    Do not take that wrong;
    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
    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:
    If you sort this, you'll get W because it's the rightmost greater
    element in numeric context.
    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...
     
    Eden Cardim, Nov 30, 2005
    #10
  11. Feyruz

    Feyruz Guest

    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.
     
    Feyruz, Nov 30, 2005
    #11
  12. Feyruz

    Eden Cardim Guest

    I am not interested in reading rudeness. Few readers are.
    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.
    Precisely what I mentioned before.
    Thank you, by the way, I had quite some fun testing sort and re-reading
    it's documentation.
     
    Eden Cardim, Nov 30, 2005
    #12
  13. Feyruz

    John Bokma Guest

    But have no problem in writing it...
     
    John Bokma, Nov 30, 2005
    #13
  14. 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.
    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
     
    A. Sinan Unur, Nov 30, 2005
    #14
  15. Feyruz

    Eden Cardim Guest

    <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
     
    Eden Cardim, Nov 30, 2005
    #15

  16. PG is an example of a Usenet phenomenon known as a "troll".

    http://www.catb.org/~esr/jargon/html/T/troll.html

    It is best to ignore what she says, and to not post followups to her posts.
     
    Tad McClellan, Nov 30, 2005
    #16
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.