so 4 stack frames have been put on the stack one for main and three for the search method which include search(node(data val 5),9), search(node(data val 8),9),search(node(data val 9),9) ok so the final stack frame returns the node with the found data value to the caller which is the search function below it,so how does the node get returned when the frames(search methods below it just return the search function itself with parameters example

return search(tree.left,value); how does the node eventually get returned to the main method which where it is used??,I'm not too sure how the return works this way,could someone try to clear this up in simple(ish) terms?

Thanks guys much appreciated

Adam Chalkley wrote:yes I have a decent understanding of how it works.

Alright, so what you don't understand in particular then? I am slightly confused

Imagine you need to go to library and get a book. There are lots of doors along the way of long coridor. So you open the first door and check if it isnt a director room where you cant go any further (tree == null). If it is not, you are looking for the book you searching. If didnt find, double checking if book title starts with letter from the first half of the alphabet or second half - that way you decide you open and go though the left or right doors for further search. So you defined you need to go right, ok, opened the doors and double check again if it isnt a director room, if not, looking for the book. Hey, you found the book. What you do next. Get the book and come back to the main hall all the way back through the opened doors you came from. Once you come to the main hall, you open the book and read it.

Adam Chalkley wrote:..but I don't get how this Node or book then gets returned all the way to the calling method which is in main

Do you understand this code : ?

I agree. Here's the better link: Salvin.in

is just syntactic sugar for:

What exactly is your confusion about ?

I agree. Here's the better link: Salvin.in

salvin francis wrote:Well, I think I misunderstood you. What I meant to explain is that

is just syntactic sugar for:

What exactly is your confusion about ?

what I don't understand is basically how the found node is returned,for example when we find the node in our search method I understand that the node is returned to the calling method(the activation stack frame before itself) but then how is that node passed to the next calling method and then all the way to the main method with the call Node search = main.search(newNode, 8); or System.out.println(main.search(newNode, 8).data);

thanks

Bear Bibeault wrote:

Adam Chalkley wrote:the three below it return search(tree.left,value);?

As explained, that returns theresultof calling the method -- and what is that?

that would be 8 which is the answer I'm looking for but I'm still confused as to how it's returned ie in my second example number equals 0 but I expected number to = 10 as the first calling method was 10

sorry I'm just so confused about what and how the data actually returns =(

thanks for all the help much appreciated

output:

I agree. Here's the better link: Salvin.in

Adam Chalkley wrote:

that would be 8 which is the answer I'm looking for but I'm still confused as to how it's returned ie in my second example number equals 0 but I expected number to = 10 as the first calling method was 10

First, can you explain to us why it would be 8? Totally confused...

As for why it returns zero, and using Knute's syntax...

Henry

Adam Chalkley wrote:

I know I'm probably beating a dead horse here but how come 0 is returned all the way to main(ie how come number will equal 0 when we say number = recur(10);

It is *not* a zero that is returned all the way to main.... each recursive step is returning it's own result, and it happens to be zero. Specifically...

1. recur(0) is returning the value of it's number parameter, which is zero

2. recur(1) is returning the result of recur(0). This is a recursive call of one less than the parameter, or one less than 1, or recur(0).... *and* from the previous point, we know that recur(0) is zero, so hence, it is returning zero.

3. recur(2) is returning the result of recur(1). This is a recursive call of one less than the parameter, or one less than 2, or recur(1).... *and* from the previous point, we know that recur(1) is zero, so hence, it is returning zero.

Do you see the pattern yet?

Henry

Henry Wong wrote:

Adam Chalkley wrote:

I know I'm probably beating a dead horse here but how come 0 is returned all the way to main(ie how come number will equal 0 when we say number = recur(10);

It is *not* a zero that is returned all the way to main.... each recursive step is returning it's own result, and it happens to be zero. Specifically...

1. recur(0) is returning the value of it's number parameter, which is zero

2. recur(1) is returning the result of recur(0). This is a recursive call of one less than the parameter, or one less than 1, or recur(0).... *and* from the previous point, we know that recur(0) is zero, so hence, it is returning zero.

3. recur(2) is returning the result of recur(1). This is a recursive call of one less than the parameter, or one less than 2, or recur(1).... *and* from the previous point, we know that recur(1) is zero, so hence, it is returning zero.

Do you see the pattern yet?

Henry

yes I finally see the pattern,took me way too long but I got it =)

now I'm going to see if I can figure out the example before using an object instead of returning a number with this knowledge,

thanks for sticking with me guys =)

Knute Snortum wrote:Maybe this will help:

Going back to this I now have a much better understanding of how recursion works but what I don't understand how it returns the found node all the way back to the caller in main,isn't return search(tree.left,value);?

or is return search(tree.left,value) == tree(the found node) and lets say if there is four stack frames like in the above example each return search(tree.left,value); returns tree(the found node) if this is the case how is that possible?

thanks again

Adam Chalkley wrote:

Going back to this I now have a much better understanding of how recursion works but what I don't understand how it returns the found node all the way back to the caller in main,isn't return search(tree.left,value);?

no

or is return search(tree.left,value) == tree(the found node)

yes

and lets say if there is four stack frames like in the above example each return search(tree.left,value); returns tree(the found node) if this is the case how is that possible?

What's not possible about it? Each

`return`returns the value of tree back to main.

All things are lawful, but not all things are profitable.

@OP

Here's how your tree looks like after you construct it. P.S. thanks to Knute for the implemented 'text' tags.

Now, what you're passing in to your search method is a full tree (exactly as above) and a node value you are looking for. (I ignore the fact that your Tree class implementation is nothing else as a holder of two methods which serves tree, but it doesn't represent tree as such.)

So, after you pass in, what is happening next. You mentioned you understood how the search goes on and on. Basically you find what you are looking for after the first recursive call, and what you get as a result back is:

1st part

2nd part