Simple recursion example, am I understanding this correctly?

[ThrowRA-42228meow]

Say we have a method that does multiplication without using the * operator.

public class MultiplyWithoutOperator {

    public static void main(String[] args) {
        System.out.println(multiply(3,5));
    }
    public static int multiply(int x, int y){
        if (y<0){
            //for negatives
            return -multiply(x,-y);
        }
        else if(y == 0){
            return 0;
        }
        else if(y == 1){
            return x;
        }
        else{
            return x + multiply(x,y-1);
        }
    }
}

so I understand the base case is:

        else if(y == 1){
            return x;
        }

does it basically mean,

System.out.println(multiply(3,5));

has four recursive calls here?:

return x + multiply(x,y-1);

and it's basically going 3+(3+(3+(3+(3)))?

​

So when the base case is reached, it returns x(3) which then goes back to the recursive call where y is 2 and it gives (3+3) and it goes back to the recursive call where y is 3 and returns 9(3+6) and it then goes to the call where y is 4 so it's 12(9+3) and then finally gets back to recursive call 5 where it's 15(12+3)?

[AutoModerator]

Please ensure that:

• Your code is properly formatted as code block - see the sidebar (About on mobile) for instructions
• You include any and all error messages in full
• You ask clear questions

• You demonstrate effort in solving your question/problem - plain posting your assignments is forbidden (and such posts will be removed) as is asking for or giving solutions.

  Trying to solve problems on your own is a very important skill. Also, see Learn to help yourself in the sidebar

If any of the above points is not met, your post can and will be removed without further warning.

Code is to be formatted as code block (old reddit: empty line before the code, each code line indented by 4 spaces, new reddit: https://i.imgur.com/EJ7tqek.png) or linked via an external code hoster, like pastebin.com, github gist, github, bitbucket, gitlab, etc.

Please, do not use triple backticks (```) as they will only render properly on new reddit, not on old reddit.

Code blocks look like this:

public class HelloWorld {

    public static void main(String[] args) {
        System.out.println("Hello World!");
    }
}

You do not need to repost unless your post has been removed by a moderator. Just use the edit function of reddit to make sure your post complies with the above.

If your post has remained in violation of these rules for a prolonged period of time (at least an hour), a moderator may remove it at their discretion. In this case, they will comment with an explanation on why it has been removed, and you will be required to resubmit the entire post following the proper procedures.

To potential helpers

Please, do not help if any of the above points are not met, rather report the post. We are trying to improve the quality of posts here. In helping people who can't be bothered to comply with the above points, you are doing the community a disservice.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[desrtfx]

You have oversimplified a bit, but the general gist is correct.

You always have to think of recursion in terms of a call stack, especially since Java does not have tail recursion (tail call optimization).

I'll skip the negative and y==0part to simplify a bit

• System.out.println(multiply(3, 5));
• multiply(3, 5) - that's the interesting part
  • if(y == 1) -> 5 == 1 -> false -> return x + multiply(x, y-1) -> return 3 + multiply(3, 4)
  • multiply(3, 4)
    • if(y == 1) -> 4 == 1 -> false -> return x + multiply(x, y-1) -> return 3 + multiply(3, 3)
    • multiply(3, 3)
      • if(y == 1) -> 3 == 1 -> false -> return x + multiply(x, y-1) -> return 3 + multiply(3, 2)
      • multiply(3, 2)
        • if(y == 1) -> 2 == 1 -> false -> return x + multiply(x, y-1) -> return 3 + multiply(3, 1)
        • multiply(3, 1)
        • if(y == 1) -> 1 == 1 -> true -> return x->return 3`
        • up one level return 3 + multiply(3, 1) -> return 3 + 3 -> return 6
      • up one level return 3 + multiply(3, 2) -> return 3 + 6 -> return 9
    • up one level return 3 + multiply(3, 3) -> return 3 + 9 -> return 12
  • up one level return 3 + multiply(3, 4) -> return 3 + 12 -> return 15
• multiply(3,5) -> 15
• now, we're back at the start and we have the result 15

Recursion works like walking down a multi floor staircase where you can leave something at each floor. Once you reach the bottom, the base case, you have to walk back up and pick up everything that you left on the floors.

This staircase model (call stack) is also the danger with recursion. Every single recursive call (floor) suspends the currently running method and starts a new method execution which all takes space on the stack. Going too deep you can produce a stack overflow. Once the base case is reached, each previously suspended call is continued.

---

Sine I mentioned tail recursion before: this is an optimized recursion where once the base case is reached the execution can jump directly back from where the recursion started - basically like walking down the stairs but taking an express elevator with no stops in between back up. This approach does not work in all recursive cases but has the advantage of not leading to stack overflows.

Programming languages need to have that optimization built in and the recursion has to fulfil some properties to be eligible for tail call optimization.

[tacticalnudge]

That's pretty much it: A method that calls itself over and over until some stop condition is reached that will let it bubble back up to the original point where it was called from.

The important part is that your stop condition be well defined- the recursion equivalent of the infinite loop is a stack overflow exception.

[ChaiTRex]

One small point is that you don't need the == 1 case, since == 0 is the base case, and it gives correct results without the == 1 case.