• Post Reply Bookmark Topic Watch Topic
  • New Topic

Recursive Methods  RSS feed

 
Felix Mauser
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I seem to have a severe blockage in my brain regarding the following....

public static int powR(int x, int exp){
if(exp ==0)
return 1;
else
return x * powR(x, exp-1);
}

For the life of me I cannot understand why this won't always return 1.

Thanks!
 
fred rosenberger
lowercase baba
Bartender
Posts: 12563
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What are you passing in?

If you make this call with

powR(5,3)

what will happen?

"if (exp == 0)" is false since exp is 3. so, we go into the else.

this will return (5 * <whatever powR(5, 2) returns>)

ok, what does powR(5,2) return?

it returns (5 * powR(5,1)), which returns (5 * powR(5,0)), which returns 1.

so basically, we get

powR(5,3) =
5 * powR(5,2) =
5 * ( 5 * powR(5,1)) =
5 * ( 5 * ( 5 * powR(5,0))) =
5 * ( 5 * ( 5 * (1))) =
5 * ( 5 * ( 5 )) =
5 * (25) =
125

[ December 14, 2006: Message edited by: fred rosenberger ]
[ December 14, 2006: Message edited by: fred rosenberger ]
 
Felix Mauser
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Oooooooh. ok. that makes sense.

Thanks!
 
fred rosenberger
lowercase baba
Bartender
Posts: 12563
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i always find recursion difficult. it can be very powerful, but it can also be a major headache.

</2-cents>
 
Felix Mauser
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
yeah, I think I am locked into the loop concept, so I couldn't understand how the values were being "held" for each recursive loop. But it seems you are just "opening up" or "running" another instance of the method until you reach the base case. I think.
 
fred rosenberger
lowercase baba
Bartender
Posts: 12563
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
that's EXACTLY right. just like any other method calling a method calling a method, they stack up. Each higher one gets put on hold until the lower ones complete (or vice versa, depending on how you think of it). When you get a return value, you then continue with the next one up in the stack, until you get back to the top.

a recursive method can build up this stack pretty fast, and can crash your program if it uses too much memory.
 
Nathan Leniz
Ranch Hand
Posts: 132
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I found a really good tutorial on recursion that breaks the process down Barney style (so just about my level ). If you'd like a copy of it Felix, just send me a private message.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!