Understanding how this recursive method works [duplicate]

Question

Can someone please explain how this method works? I tried adding System.out.print statements but it didn't get me anywhere and I simply cannot seem to get my head around it at the moment.

public static double recursive(double x, double y, int n) {

    if(n==0) {
        return x;
    }

    return recursive(x, y, n-1) * (1+y);
}

EDIT: I have realised that I looked at this method from the wrong perspective (not sure how this happened but it did) and in a moment of panic I decided to ask for the wisdom of the masses.

The explanations for this are very clear and concise, also in regard to recursion in general, which is why I'd like to keep the post up rather than delete my moment of tomfoolery.

Answer 1

The method multiplies x by 1 + y an n number of times. In other words, the method will return x*(1+y)^n in the end. This is given that the original n > 0. If n is originally less than 0, the method will recurse infinitely.

Explanation: When the method "enters" recursion and calls itself, it will do so n number of times since we decrease n by 1 until n equals 0. When n finally reaches 0, the innermost call of recursion will return x. Each consecutive call will multiply the output of the previous call by 1+y.

Answer 2

Since I can't comment, I try to answer the question this way.

If you can't follow the code debugging, try to do it manually. Let's assume we have the following values:

| x | y | n |
| 5 | 2 | 2 |

Now call the methode with those values and play it through in your mind. Since n isn't 0 in the first step it would call the methode again with n-1. This is repeated as often as n is equal 0. With each nested call you need to muliply the result with (y-1). So the way for the values above would be:

`>Inital call: recursive(5, 2, 2) -> n != 0

Rec call 1-> recursive(5, 2, 1) * (3) -> n != 0

Rec call 2-> recursive(5, 2, 0) * (3) -> n == 0 return x -> return 5`

Now you need to go backwards so you calculate 53 = 15 ( Return Value of rec Call 1). This result you need to calculate again so we have 15 3 = 45 as the result of the inital methode.

I hope that you can figure out the real function of the methode.

Answer 3

This is not the picture of your algorithm, but it can help you understand recursive calls' concept.

On the right side you have order of the calls (from top to down), and on the left side, you have order of returns (from bottom to top).

Method calls itself with n-1 argument.

1. Pay attention, that you have a base case, which is n==0;

2. Now pay attention, that when a particular method starts execution, at some point, it calls another instance of itself, but with smaller n;

3. This calling yourself pattern continues with one less n each time, until you hit your base case;

4. The moment call stack hits the n==0 base case, method calls will start unwinding: last will return, which will enable previous-to-last to return, and so on, until your very first invocation returns and method returns.

This call behaviour is called Last In First Out (LIFO).