1

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.

h4ckerlinguist
  • 93
  • 7
  • 1
    This will call itself N times (n-1 in fact as first call will be from the outside - but all interations will be of N times). What seems to be the problem? – Antoniossss Mar 23 '21 at 07:14
  • 1
    x * (1+y) ^ n... Why one would do that is very unclear... As well it is unclear what is unclear for you in this code... – Alexei Levenkov Mar 23 '21 at 07:16
  • 1
    Do you understand how *any* recursive method works? – Karl Knechtel Mar 23 '21 at 07:45
  • Yes, I have realised my mistake now in understanding this. Despite the very obvious name of the method I wasn't looking at it recursively which in hindsight was a really dumbass move but it is quite early here so maybe that's the reason. – h4ckerlinguist Mar 23 '21 at 07:47
  • 1
    To understand recursion a simple trick is : Suppose each time the function `recursive` is invoked a NEW copy of the function is created i.e. `recursive` function calling `recursive1` , `recursive1` calling `recursive2` and so on. There will be a point where the base condition will become true and `n == 0` will become true, suppose it is the `recursiveK` function so it will return x to `recursiveK-1` and this returned value will replace the function call, do the multiplication with `(1+y)` and return to `recursiveK-2` and so on till we reach `recursive` which will return to the main caller. – nits.kk Mar 23 '21 at 07:51

3 Answers3

2

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.

mushycow
  • 86
  • 2
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.

Sheena
  • 107
  • 9
1

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.

enter image description here

  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).

Giorgi Tsiklauri
  • 9,715
  • 8
  • 45
  • 66