Re: recursion

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?

Comment on Re: recursion Select or Download Code

Replies are listed 'Best First'.

Re: Re: recursion
by bronto (Priest) on Jun 23, 2002 at 20:07 UTC

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]


good chemistry is complicated, and a little bit messy -LW
	PerlMonks