• Post Reply Bookmark Topic Watch Topic
  • New Topic

Help with recursive method  RSS feed

 
Daniel Ungerfält
Ranch Hand
Posts: 53
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi!
Can someone please explain to me how this works? Why is the result 4 ?
Should´nt it be someting like: 16/2 = 8/2 = 4/2 = 2 /2 = 1, return 1 + 1 = 2?, or 1 + the results ( 1+ 8 ,1+4, 1+2 ,1+1 = 20 ) ??
Cant figure it out.. Need a step by step explanation.

 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Daniel Ungerfält wrote:
Should´nt it be someting like: 16/2 = 8/2 = 4/2 = 2 /2 = 1, return 1 + 1 = 2?, or 1 + the results ( 1+ 8 ,1+4, 1+2 ,1+1 = 20 ) ??
Cant figure it out.. Need a step by step explanation.


Well, you got the calls correct. You just now need to get the returns correct. The returns are ... 0 --> 1 + 0 --> 1 + 1 --> 1 + 2 --> 1+ 3 --> 4.

Henry
 
Daniel Ungerfält
Ranch Hand
Posts: 53
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ok. so the only thing that returns is apparently the 1 x number of "loops" (1X4 = 4). If I put 2+ infront i return 8 of course..
But now my question is why it does´nt return the value of inverpower(n/2), like when you put inverpower(n-1), (n+1) etc,, it will return that values as well.. Why is that?
 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Daniel Ungerfält wrote:
But now my question is why it does´nt return the value of inverpower(n/2), like when you put inverpower(n-1), (n+1) etc,, it will return that values as well.. Why is that?


By "doesn't return the value of inverpower(n/2)", I am assuming that you were assuming that something else is to be returned? We don't know what you expect to be returned, so can't answer your question... except, as coded, it is returning the correct value.

Henry
 
Daniel Ungerfält
Ranch Hand
Posts: 53
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Henry Wong wrote:
Daniel Ungerfält wrote:
But now my question is why it does´nt return the value of inverpower(n/2), like when you put inverpower(n-1), (n+1) etc,, it will return that values as well.. Why is that?


By "doesn't return the value of inverpower(n/2)", I am assuming that you were assuming that something else is to be returned? We don't know what you expect to be returned, so can't answer your question... except, as coded, it is returning the correct value.

Henry


For me: return 1 + inverse2Power(n/2); looks like return the number 1 plus the value in the methods argument --> (inversePower(n/2)..

 
fred rosenberger
lowercase baba
Bartender
Posts: 12563
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Daniel Ungerfält wrote:For me: return 1 + inverse2Power(n/2); looks like return the number 1 plus the value in the methods argument --> (inversePower(n/2)..


"inversePower(n/2)" is a method call. so it effectively gets replaced with the int value that you get when inversePower(n/2) is called. It's as if it were written this way:


 
Joe Bishara
Ranch Hand
Posts: 175
17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
the result of inverse2Power(16) is 1 + inverse2Power(8)
the result of inverse2Power(8) is 1 + inverse2Power(4)
the result of inverse2Power(4) is 1 + inverse2Power(2)
the result of inverse2Power(2) is 1 + inverse2Power(1)
the result of inverse2Power(1) is 0


 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Joe, Nice diagram. You earned a cow.


BTW, in reading this thread again, I think the OP is thinking that the results should be the sum of 8, 4, 2, 1; ie. the sum of the parameters, and not what was returned from the method call. Or in other words, the OP was thinking about the value of "n/2" and not the value returned from the inverse2power(n/2) method call?

Henry
 
Joe Bishara
Ranch Hand
Posts: 175
17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks.
 
Daniel Ungerfält
Ranch Hand
Posts: 53
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Henry Wong wrote:Joe, Nice diagram. You earned a cow.


BTW, in reading this thread again, I think the OP is thinking that the results should be the sum of 8, 4, 2, 1; ie. the sum of the parameters, and not what was returned from the method call. Or in other words, the OP was thinking about the value of "n/2" and not the value returned from the inverse2power(n/2) method call?

Henry


Exactly! I Still cant figure out how it works. Cause if you look at it, it looks like 1 + (16/2). And my mathematic brain read this as (1 + (16/2)) + (1 + (8/2)) and so on...
 
fred rosenberger
lowercase baba
Bartender
Posts: 12563
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Daniel Ungerfält wrote:Exactly! I Still cant figure out how it works. Cause if you look at it, it looks like 1 + (16/2). And my mathematic brain read this as (1 + (16/2)) + (1 + (8/2)) and so on...


it's not " (1 + (16/2))" it is actually

(1 + inverse2Power(16/2))

which is actually

(1 + inverse2Power(8))

so when the JVM gets to this line, it says "ok..i know what 1 is. I need to add something to it. Oh...I need to call a function. Before I finish doing this addition, I need to execute inverse2Power with a parameter of 8. I'll hold off on completing this addition until I figure out what that function call returns."

So this method is suspended until we get the result from the call to inverse2Power(8). That starts to get computed until we have to call inverse2Power(4)...etc.

Here's another way to look at it.

if we simply called the method inverse2Power(1), it will clearly return 0. so now, any time we see inverse2Power(1), we can replace it with 0.

Now think about calling inverse2Power(2). Looking at the code, we should get to this line:


where n = 2.
so that becomes

which becomes

which from above we know is

So, inverse2Power(2) will return 1. we now can make this substitution. Let's call inverse2Power(4)
that will get us to

which becomes

which becomes

which becomes

so inverse2Power(4) we now know is 2.
We can keep working our way up to find that
inverse2Power(8) -> 1 + inverse2Power(4) -> 1 + 2 -> 3
and so
inverse2Power(16) -> 1 + inverse2Power(8) -> 1 + 3 -> 4
 
Daniel Ungerfält
Ranch Hand
Posts: 53
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
inverse2Power(16) -> 1 + inverse2Power(8) -> 1 + 3 -> 4


Thanks alot!
Starting to understand, but how can inverse2Power(8) be 1 +3 and not 1 +4 ? inverse2Power(4) seems logic when you say 1+2 -> 3...
 
fred rosenberger
lowercase baba
Bartender
Posts: 12563
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Daniel Ungerfält wrote: how can inverse2Power(8) be 1 +3 and not 1 +4 ?

it's not.

inverse2Power(8) is equal to 3 (and not "1 + 3")

inverse2Power(4) is equal to 2.

inverse2Power(2) is equal to 1.

inverse2Power(1) is equal to 0.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!