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

Recursive Methods

Greenhorn
Posts: 11
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!

lowercase baba
Bartender
Posts: 12613
50
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
Oooooooh. ok. that makes sense.

Thanks!

fred rosenberger
lowercase baba
Bartender
Posts: 12613
50
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
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: 12613
50
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.

Ranch Hand
Posts: 132
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.