The way to understand a recursive program is by the following steps:
- Find some measure by which the recursive calls are for "smaller" instances of the problem.
- Show that when it reaches the smallest instances, it gives the correct result (directly)
- Assuming the recursive calls do their job correctly, their results are combined to get the correct solution for the overall problem.
You should try some (small) cases by hand, to see what is going on (and find clues on the above points). When writing a recursive program, you'll have to think about the above items exactly the same way.
A correctness proof will have to consider essentially the same points, just more formally. No "mathematical formulas" are needed, just clear reasoning.
In your case, $n$ is an obvious measure of "size", that gets reduced each call. The rest is left as an exercise. ;-)