Basilides has asked for the wisdom of the Perl Monks concerning the following question:

i'm quite new to perl & haven't really used objects in perl before. i'm just trying to traverse a simple binary tree. the following will find the leftmost node, and print it out, but then it doesn't seem to GO anywhere--ie it doesn't seem to print out the higher nodes which called it, and move along to the right. anyone know what's up? is it something peculiar to perl (or have i just done something wrong)? 
sub display
{    my $self = shift;
    $self->displaynames($self->{root});
}

sub displaynames
{    my $self = shift;
    $head = shift;
    print $head->{Val}, " ";
    if (defined ($head->{LRef}))
    {    $self->displaynames($head->{LRef});
    }
    print $head->{Val}, "\n";
    if (defined ($head->{RRef}))
    {    $self->displaynames($head->{RRef});
    }
}

[download]

edited: Mon Jun 24 14:42:19 2002 by jeffa - title change

Replies are listed 'Best First'.
•Re: recursion
by merlyn (Sage) on Jun 23, 2002 at 15:48 UTC
[reply]
[d/l]
[select]
Re: recursion
by Basilides (Friar) on Jun 23, 2002 at 15:26 UTC
    oh wait, i left a print line in there that you don't need to see--from when i was trying to debug it. proper routine, which doesn't work, is: 
    sub display
{    my $self = shift;
    $self->displaynames($self->{root});
}

sub displaynames
{    my $self = shift;
    $head = shift;
    if (defined ($head->{LRef}))
    {    $self->displaynames($head->{LRef});
    }
    print $head->{Val}, "\n";
    if (defined ($head->{RRef}))
    {    $self->displaynames($head->{RRef});
    }
}

    [download]
[reply]
[d/l]
[select]
Re: recursion
by Basilides (Friar) on Jun 23, 2002 at 15:45 UTC
    ok, i add some nodes (the addnode routine works, i know), and then call display: 
    $q = new Tree;
$q->addnode(4);
$q->addnode(3);
$q->addnode(5);
$q->addnode(14);
$q->addnode(15);
$q->addnode(7);
$q->addnode(19);
$q->display;

    [download]
    so the tree should look like this: 
      4
 / \
3   5
     \
     14
     /\
    7  15
        \
        19

    [download]
    So i'd expect the display routine to list the numbers in order, starting with the lowest. In fact, what I get is: 
    3
3

    [download]
    What seems to be happening is that it correctly finds it's starting point, at which point there are 2 levels of recursion. It prints the node value, then goes back to the calling level, but still refers to the lowest level node. So print $head->{Val}, "\n"; still, for some reason prints '3'. Incidentally, if i run it from right to left, i get 
    19
19
19
19
19

    [download]
    Do you see what i mean? When a subroutine ends and passes control back up to the calling level, is $head not being returned to it's value in the calling routine?
[reply]
[d/l]
[select]

      That's exactly what merlyn told you: you don't "localize" $head (I should see "lexicalize" maybe, but "localize" should be clearer... maybe :-). That way you overwrite the same $head variable again and again when you go down the tree and, when it finally reaches the leaf, it goes up... printing always the same values (count them: you printed one 19 per level).

      One fundamental thing when you write recursive code is to properly localize the variables in play and never use global variables unless you are really sure you can't do without. If you use my, every call of the subroutine gets it's own clean $head, which is exactly what you want.

      Even if Perl allows you not to declare variables, it doesn't mean you should do it. I learned on my own expenses that it's not safe to work without use strict, unless you are writing a one liner.

      Ciao!
      --bronto

[reply]
[d/l]
[select]
Re: recursion
by jepri (Parson) on Jun 23, 2002 at 15:36 UTC
    I can't comment on your data structures, because I can't see them. But basic program flow from your example confirms that it will never work properly. You call displaynames with one variable:

    $self->displaynames($self->{root});

    [download]

    But displaynames needs two variables to work:

    
sub displaynames
{       my $self = shift;
        $head = shift;

    [download]

    If $head isn't defined, the rest of the routine does not run, and no 'child' nodes are called. Either call displaynames with two arguments, or remove those if statements.

    Update: And either you are running without strict or you have defined '$head' as a global, both are bad.

    ____________________
    Jeremy
    I didn't believe in evil until I dated it.

[reply]
[d/l]
[select]
      Be very careful - you are wrong. Since he is calling the method using $self->, he implicitly passes $self as the first parameter. Therefor, his call to displaynames() will work as it is. Your update is the real reason, as merlyn++ pointed out.

      Makeshifts last the longest.

[reply]
        Ack! I'm stupid as charged, except for the bit that should read "real reason, as merlyn++ and jepri-- pointed out". I don't go around copying other peoples nodes without credit.

        ____________________
        Jeremy
        I didn't believe in evil until I dated it.

[reply]

Back to Seekers of Perl Wisdom