In the simplest sense, recursion is when a method calls itself. Writing recursive methods is not a task for the AP Exam. Truth be told, writing a meaningful recursive method can be difficult for many beginner programmers. With that said, being able to trace recursive methods is all you need to do for the AP Exam although you are encouraged to try some of the simpler problems in the Practice! Recursion is most useful when you can break a problem up into small pieces. The idea of the method calling itself is actually the method breaking the problem up into small pieces solved by each method call.

public static int factorial(int n){
    if (n == 0)
        return 1;
    else
        return n * factorial(n-1);
}

The Factorial method is a recursive method that is often introduced when discussing recursion. Recall that the factorial of a number n is n * (n -1)*(n-2)*(n-3). Every recursive method has a base case. The base case stops the recursion otherwise you will get infinite recursion aka a stack overflow! Given some problem definition for some input, the base case is the simplest case for which the method returns the answer rather than calling itself to find the answer. The base case for factorial is 0 as shown above. The factorial of 0 is 1 and is considered a trivial case by definition. It is possible for methods to have more than just one base case.

Let's trace the factorial method with a call to factorial(3).

public static int factorial(int n){
    if (n == 0)
        return 1;
    else
        return n * factorial(n-1);
}
A call to factorial(3) returns 3 * factorial(3-1). 

You will see this by just following the body of the factorial method from top-to-bottom. As long as you see a call to the method, you need to continue tracing what that method call returns until you hit a base case that stops the recursion.

factorial(3) returns 3 * factorial(2)
factorial(2) returns 2 * factorial(1)
factorial(1) returns 1 * factorial(0)

Backtracking is going from the bottom layer of the tracing above to see ultimately what the result is!
factorial(3) returns 3 * result of row below => 3 * 2
factorial(2) returns 2 * result of row below => 2 * 1
factorial(1) -> 1*factorial(1) => 1 

public static int mystery(int n){
    if (n == 0)
        return 1;
    else
        return 3 * mystery (n - 1);
}

Tracing for mystery(4):

mystery(4) returns 3 * mystery(3)
mystery(3) returns 3 * mystery(2)
mystery(2) returns 3 * mystery(1)
mystery(1) returns 3 * mystery(0)
mystery(0) returns 1

Backtracking from the bottom row you get:
mystery(4) returns 3 * mystery(3) = 3 * 27 = 81
mystery(3) returns 3 * mystery(2) = 3 * 9 = 27
mystery(2) returns 3 * mystery(1) = 3 * 3 = 9
mystery(1) returns 3 * mystery(0) = 3 * 1 = 3
mystery(0) returns 1 

public static int strMethod(String str){
    if (str.length() == 1) return 0;
    else{
        if (str.substring(0,1).equals("e")) return 1 + mstrMethod(str.substring(1));
           else return strMethod(str.substring(1));
    }
}

Tracing call to strMethod("very"):

strMethod("every") returns 1 + strMethod("very")
strMethod("very") returns strMethod("ery")
strMethod("ery") returns 1 + strMethod("ry")
strMethod("ry") returns strMethod("y")
strMethod("y") returns 0

Backtracking from last row:
strMethod("every") returns 1 + strMethod("very") = 2
strMethod("very") returns strMethod("ery") = 1
strMethod("ery") returns 1 + strMethod("ry") = 1 + 0
strMethod("ry") returns strMethod("y") = 0
strMethod("y") returns 0

The two recursive methods you should familiarize yourself with for the AP exam are binarySearch and MergeSort.