Java Recursive Method how does it work?

Question

I'm relatively new to Java programming and I've just started learning recursion, but I can't seem to figure out how this method works in my head.

   private static int mystery(int w) {
    {
        if (w < 0) return 0;
        int x = mystery (w-2);
        return w - x;
    }
}

Whenever a variable like 100 is put in, it outputs 50. When 200 is input, it outputs 100. When 2 is input, it outputs 2. When 25 is input, 13 is output. I'm not sure how this method works, and I'm trying to wrap my head around it.

The way I currently view it, if you put in 100, it'll bypass the first return statement since it is greater than 0. when it gets to the second line, it'll do 100-2, which brings in 98, then goes to the third line and does 100 - 98 = 2. Which is then returned to the original call.

I know I'm messing up on the second line of the method where the mystery (w-2) is. I assume it would bring back the result of w-2 to the beginning of the method again, and it would continue to do the method over and over again until w is smaller than 0, which should output 0 again regardless of the answer. But that's not what happens, and I don't know why.

Can anyone explain what is going on here?

Read the SICP book, it explains this and also many other important ideas in programming. Also make sure to format your code properly, or some angry programmers will downvote your question. — Display Name, Mar 21 '15 at 21:16
It doesn't go to the third line until the second line is resolved. In the above case, when you reach mystery(w-2), you call mystery(98)...and then inside of that call, it'll call mystery(96) at the second line... — MingShun, Mar 21 '15 at 21:17
…because `w` is int, and the used stack size is proportional to `w` — Display Name, Mar 21 '15 at 21:19
Endgame wise, you'll call mystery(-2), and that's when things roll back up. Mystery(0) will return (0-0). Mystery(2) will return (2-0). Mystery (4) will return(4 - Mystery(2)) = 2. Mystery(6) will return (6 - Mystery(4)) = 4. Mystery(8) will return (8 - Mystery(6)) = 4. Mystery(10) will return (10 - Mystery(8)) = 6. Based on this pattern and judging that 100 % 2 is even, Mystery(100) will return (100 - Mystery(98)) or...50. — MingShun, Mar 21 '15 at 21:19
Showing you a link isn't enough to warrant for an answer, and are many resources on this, as recursion is a concept in computer science and programming, not just to Java. Here's a video by Computerphile I felt helped visualize and understand recursion: https://www.youtube.com/watch?v=Mv9NEXX1VHc — matrixanomaly, Mar 21 '15 at 21:23
Possible duplicate of [Understanding how recursive functions work](http://stackoverflow.com/questions/25676961/understanding-how-recursive-functions-work) — , May 27 '16 at 18:46

score 13 · Answer 1 · answered Mar 21 '15 at 21:24

What you are missing is that on the second line it doesn't just do w - 2, but calls itself with w - 2. It doesn't go further until the call returns. And the second call calls itself if w isn't < 0 and so on until you reach value lower than 0 and then return. The execution will go like this, if you visualize it:

mystery(10)
    > skip first line
    > x = mystery(8)
        > skip first line
        > x = mystery(6)
            > skip first line
            > x = mystery(4)
                > skip first line
                > x = mystery(2)
                    > skip first line
                    > x = mystery(0)
                        > skip first line
                        > x = mystery(-2)
                            > return 0
                        > return 0 - 0 (0)
                    > return 2 - 0 (2)
                > return 4 - 2 (2)
            > return 6 - 2 (4)
        > return 8 - 4 (4)
    > return 10 - 4 (6)

With example of w = 10. I hope you understand it better now.

When debugging recursion it can be useful to send this same text to the console. Adding an indent parameter that grows with every call and some `system.out.printlin`s should be enough to do it. — candied_orange, Mar 21 '15 at 21:57

score 0 · Answer 2 · answered Mar 21 '15 at 21:28

   private static int mystery(int w) {
    {
        if (w < 0) return 0;
        int x = mystery (w-2);
        return w - x;
    }
}

Let's imagine that we call mystery(3). What happens? w<0) is false, so we don't return 0. In the next line, we call some function called mystery using the value 3-2=1 as its argument. Despite the fact that this function we've called happens to be the same one we've just called, it's still an ordinary function call, and it returns a value. It does this by calling the function called mystery, this time using the value -1 as the argument. And this time w<0 is true, so we just return 0. Now we're back in the second call to mystery, and we've set x = 0. So that call returns w - 0 = 1. That puts us back in the first call, and now x = 1, so we return w-x = 3-1 = 2.

You might want to take a few minutes and work through this using w=4 and see what you get - this will help you understand how the recursive calls work. After you've done this, I suggest you add a print statement or two in the function to tell you where you are and what's happening, and that'll also help - but do it on paper first.

score 0 · Answer 3 · answered Mar 21 '15 at 21:39

The two given answers are excellent. Both focus on the way how to get a grasp of what recursion is. The problem with recursion is, that it is so unnatural to one who do not know what recursion is, or do not know someone who does. It's like a snake eating itself again and again.

The best way to understand recursion is to write down the calls to a recursive method, by noying the current state when it's called, and after the call write the result back. You stack up the calls and that's also the way to not used recursion at all.

So do not try too hard to understand recursion at first but first focus on the program flow. If you have seen enough recursions, it will come to you.

Java Recursive Method how does it work?

3 Answers3

Linked