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(n1); }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)*(n2)*(n3). 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. 
Tracing FactorialLet'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(n1); } A call to factorial(3) returns 3 * factorial(31).You will see this by just following the body of the factorial method from toptobottom. 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) 
Tracing Practicepublic 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 
String Tracingpublic 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 
The two recursive methods you should familiarize yourself with for the AP exam are binarySearch and MergeSort.
