Recursion - What does it do

I'm at my wit's end... I understand the easier examples of recursion, but I when it gets tricky I don't have a clue. Here is an example. I would be glad if someone can say what it does. What does the compiler do...

public static char mystery(String s, int n, int m)
{
if (n==1) return s.charAt(m);

cha开发者_如何学编程r first = mystery(s, n/2, m*2);
char second = mystery(s, n/2, m*2 +1);

System.out.print(first + " " + second + " ");

return first; 
}

What is printed when the method is called with: mystery("fredpass", 5, 1)

The answer is p a s s p s

I don't have a CLUE how they get there...

Would REALLY appreciate it if someone can help me with this matter. On other places on the internet they only explain factorial - easy examples. Not sure what happen if you call it twice as in char first = mystery ( blah ); and then again char second = mystery ( blah );

---

Just trace the calls by hand:

mystery(5, 1)
    first = mystery(2, 2)
        first = mystery(1, 4) = 'p'
        second = mystery(1, 5) = 'a'
    second = mystery(2, 3)
        ...

and so on. Give yourself enough paper to draw a complete picture of the call stack, the state of a function call, and the local variables. For example, after the innermost call in my picture prints "p a ", it returns 'p', so I would write that letter after mystery(2, 2).

---

So, you already know examples of recursion and how it can be used.

Perhaps what you are missing is why recursion works. In order to understand this you need to know what happens when a method is called. Familiarize yourself with the call stack.

In terms of what happens logically, you should just consider 'walking' across the code sequentially. When you call a method recursively, it will simply return the result and continue execution as it would in any other procedural code. Every method call however has its own scope of variables which are only valid in that particular call of the recursion.

---

Hand "executing" as described in @jleedev's answer is a useful exercise, especially if you've never done it before.

An alternative is to run the code under the control of a Java debugger, and single step the execution while examining the call stack / local variables. This is less error prone, though if you do it too quickly you might miss important details of what is actually going on.

Don't be too worried that it is a mystery to you what the mystery function actually does. It is clearly designed to be difficult to understand. (And I cannot see any point to it ... apart from being mysterious.) Most recursive functions that you are likely to encounter will do something useful, and will be easier to understand ... with experience ...

---

For every recursion there are two things to be considered

1. Every recursive method should have a base case.
2. Every recursion should progress towards this base case