programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Help with recursive method

Daniel Ungerfält
Ranch Hand
Posts: 53
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
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
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
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
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
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
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
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
Thanks.

Daniel Ungerfält
Ranch Hand
Posts: 53
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
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
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
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.