Recursion Help!

[ottilie]

Okay, I have this problem to do and I have no idea how to do it.

Refer to the method result:

public int result (int n)
{
   if (n == 1)
        return 2;
   else
        return 2 * result(n-1);
}

If n > 0, how many times will result be called to evaluate result(n) (including the initial call)? State how you figured it out.

[Chilton]

You're counting how many times the function is called recursively, correct?

If that's the case, then you'd need a counter. Still, it wouldn't just be any counter though. You'd need one that retains its value even after it's used again.

This looks like C++, so think of a what is available for you that allows a variable to retain its value when called again or just in general. Here's hoping you come to your desired solution.

"givemetehcodez" isn't going to happen. Good luck.

[abhimanipal]

Quick question were you looking for a mathematical solution or a programming kinda solution like the one described above ?

[firstPerson]

Take for example the call result(3). Trace the recursion out and get:

result(3) = result(2)*2
= result(1)*2 * 2
= 2*2*2
= 8

So you see calling result(3) calls result(2) which calls result(1).
Thus there are 3 calls to result n. If you try to generalize it,
you will see that result(n) will call result n times.

[apines]

Okay, I have this problem to do and I have no idea how to do it.

Refer to the method result:

public int result (int n)
{
   if (n == 1)
        return 2;
   else
        return 2 * result(n-1);
}

If n > 0, how many times will result be called to evaluate result(n) (including the initial call)? State how you figured it out.

Take a look at the if/else clause: If the number n equals to 1, then simply return 2 - this is whats called the stopping condition. Every other value of n - and the method will call to itself again in recursion. Try and run some numbers. For example, let's take n = 4, and see what happens.

// n equals to 4, not to one, so we will go into the else clause.
if (n == 1) 
        return 2;
   else
        return 2 * result(n-1);

Since we are going to the else clause, the method will call itself again in recursion, this time with the value of 4-1=3.

// n equals to 4, not to one, so we will go into the else clause.
if (n == 1) 
        return 2; // n equals to 3, not to one, so we will go into the else clause.
   else
        return 2 * result(n-1);

And again, the recursion continues, this time with a value of 2.

// n equals to 4, not to one, so we will go into the else clause.
if (n == 1) 
        return 2; // n equals to 2, not to one, so we will go into the else clause.
   else
        return 2 * result(n-1);

Yes, recursion again, this time with the value of 1. Now something different happens:

if (n == 1) 
        return 2; // n equals to 1, now we go inside the if clause.
   else
        return 2 * result(n-1);

We have reached the stopping condition - the recursion will not be called again. The last call to the recursion will return the value of two. The method that called it, result(2) will receive this value of 2 and will return

return 2 * result(1); // 2*2=4

2*2=4, which will be returned to the calling method, which is result(3). Again we get

return 2 * result(2); //2*4=8

Meaning the result(3) will return 8 to the calling method, result(4), which, eventually will return

return 2 * result(2); //2*8=16

The user who called result(4) will get 16, and you can count easily the number of times that the method had been called. Do you think that this analysis holds for any n>0 ?