• Post Reply Bookmark Topic Watch Topic
  • New Topic

not exactly sure how return works in this instance?  RSS feed

 
Adam Chalkley
Ranch Hand
Posts: 517
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi guys the problem I am having is with the search method of this binary tree search algorithm and more specifically with what the return does,ok lets say I enter 9 as the value to try and find like in the code,the search function will check to see if tree == null which it does not ,then it checks to see if the value equals the current nodes data value which is 5 it is greater so it goes to line of code return search(tree.right,value); tree.right is the object with the data value 8 and value is 9,the search method now runs again with these parameters its checked to see if it's equalled to null which it is not then  checked to see if the nodes data value equals the value passed in it does not it is greater so the function gets run again this time with tree.right which equals the node object with data value 9 and with the value 9,it checks to see if it equals null which it does not,then it checks to see if the data value of the current node equals the value passed in it does so it returns that node,I understand all that but this is the part that confuses me(with return),

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








 
Bear Bibeault
Author and ninkuma
Marshal
Posts: 66260
151
IntelliJ IDE Java jQuery Mac Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Adam Chalkley wrote:it just return the search function itself with parameters

No, it doesn't. It returns the result of calling the search method with those parameters.


is no different than:
 
Adam Chalkley
Ranch Hand
Posts: 517
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Moderator's comment: removed unecessarily long quote.

thanks bear,but I still don't understand how the found node gets returned ALL the way back to main,pretty confused
 
Liutauras Vilda
Marshal
Posts: 4798
330
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Adam Chalkley wrote:I still don't understand how the found node gets returned ALL the way back to main,pretty confused

Do you know what is recursion and how it works?
 
Adam Chalkley
Ranch Hand
Posts: 517
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
yes I have a decent understanding of how it works.
 
Adam Chalkley
Ranch Hand
Posts: 517
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes I have a decent understanding of recusrion but I'm just not sure how the found Node is returned all the way back to main

PS sorry I should have posted this in the original reply
 
Liutauras Vilda
Marshal
Posts: 4798
330
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 517
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
thanks Liutauras great analogy,I understand how the node(or book in this example) gets returned to the caller which is the activation frame below it but I don't get how this Node or book then gets returned all the way to the calling method which is in main

thanks =)
 
salvin francis
Saloon Keeper
Posts: 1644
37
Eclipse IDE Google Web Toolkit Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 : ?
 
Adam Chalkley
Ranch Hand
Posts: 517
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
salvin francis wrote:
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 : ?



yes I have a god grasp on it I guess.
 
Adam Chalkley
Ranch Hand
Posts: 517
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
good*
 
Adam Chalkley
Ranch Hand
Posts: 517
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
apart from Node search = main.search(newNode, 8);
          
          System.out.println(search.data);

sorry I should have put this in one post,I jump to my replies to quick.
 
salvin francis
Saloon Keeper
Posts: 1644
37
Eclipse IDE Google Web Toolkit Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, I think I misunderstood you. What I meant to explain is that


is just syntactic sugar for:


What exactly is your confusion about ?
 
Adam Chalkley
Ranch Hand
Posts: 517
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Knute Snortum
Sheriff
Posts: 4200
122
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Maybe this will help:
 
Adam Chalkley
Ranch Hand
Posts: 517
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Knute Snortum wrote:Maybe this will help:


hey Knute that does make a little more sense thanks,

just one question though the final one will return tree,the three below it return search(tree.left,value);?

thanks
 
Adam Chalkley
Ranch Hand
Posts: 517
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
also another question that might help me understand what's going on,

in this example how come number equals 0?? why would it not equal lets say 10 the last number it returns?


thanks


 
Bear Bibeault
Author and ninkuma
Marshal
Posts: 66260
151
IntelliJ IDE Java jQuery Mac Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Adam Chalkley wrote:the three below it return search(tree.left,value);?

As explained, that returns the result of calling the method -- and what is that?
 
Adam Chalkley
Ranch Hand
Posts: 517
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Bear Bibeault wrote:
Adam Chalkley wrote:the three below it return search(tree.left,value);?

As explained, that returns the result of 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
 
salvin francis
Saloon Keeper
Posts: 1644
37
Eclipse IDE Google Web Toolkit Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, here's something that might clear your doubts, I added a few sysouts to your code:




output:
 
Henry Wong
author
Sheriff
Posts: 23289
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 517
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks guys much appreciated for all the help =)

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

 
Henry Wong
author
Sheriff
Posts: 23289
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Adam Chalkley
Ranch Hand
Posts: 517
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 =)
 
Adam Chalkley
Ranch Hand
Posts: 517
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Carey Brown
Saloon Keeper
Posts: 3243
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Your recursive method behaves the same way except that the method name will be the same instead of a(), b(), and c().
 
Knute Snortum
Sheriff
Posts: 4200
122
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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. 
 
Liutauras Vilda
Marshal
Posts: 4798
330
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Don't know where I left off, but I might will start over.

@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
 
Liutauras Vilda
Marshal
Posts: 4798
330
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you would have print statement like:

What you'd get printed?
 
Liutauras Vilda
Marshal
Posts: 4798
330
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And one more, if you'd have print statement like:

What would happen now?
 
Adam Chalkley
Ranch Hand
Posts: 517
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Liutauras Vilda wrote:If you would have print statement like:

What you'd get printed?


35

 
Adam Chalkley
Ranch Hand
Posts: 517
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Liutauras Vilda wrote:And one more, if you'd have print statement like:

What would happen now?


7
 
Adam Chalkley
Ranch Hand
Posts: 517
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks guy I finally understand it =) thanks for all your help much appreciated
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!