# 11.1.6. Tracing Challenge : Recursion¶

Trace through the following recursion problems.

Consider the following recursive method:

1public static int mystery(int n)
2{
3    if (n == 0)
4        return 1;
5    else
6        return 3 * mystery (n - 1);
7}


The trace of this code for mystery(4) is shown below.

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 A


Once mystery(0) returns 1 the value for each call to mystery can now be calculated and returned.

mystery(4) returns 3 * mystery(3) = 3 * X = Y
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


Consider the following recursive method:

 1public static int strMethod(String str)
2{
3   if (str.length() == 1) return 0;
4   else
5   {
6      if (str.substring(0,1).equals("e")) return 1 +
7                           strMethod(str.substring(1));
8      else return strMethod(str.substring(1));
9   }
10}

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 B


Once strMethod(“y”) returns, the value from each recursive call on the stack can be calculated and returned.

strMethod("every") returns 1 + strMethod("very") = Z
strMethod("very") returns strMethod("ery") = Y
strMethod("ery") returns 1 + strMethod("ry") = 1 + X
strMethod("ry") returns strMethod("y") = 0
strMethod("y") returns 0


# 11.1.7. Summary¶

• A recursive method is a method that calls itself.

• Recursive methods contain at least one base case, which halts the recursion, and at least one recursive call.

• Each recursive call has its own set of local variables, including the formal parameters.

• Parameter values capture the progress of a recursive process, much like loop control variable values capture the progress of a loop.

• Any recursive solution can be replicated through the use of an iterative approach.

• Writing recursive program code is outside the scope of the course and AP Exam.

• Recursion can be used to traverse String, array, and ArrayList objects.