# 12.7. Trace Practice¶

Consider the following recursive method:

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

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

 ```1 2 3 4 5``` ```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 ```

12-6-1: What is the value of A in the trace above?

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

 ```1 2 3 4 5``` ```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 ```

12-6-2: What is the value of X in the trace above?

12-6-3: What is the value of Y in the trace above?

Consider the following recursive method:

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

12-6-4: What is the value of B in the trace above?

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

 ```1 2 3 4 5``` ```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 ```

12-6-5: What is the value of X in the trace above?

12-6-6: What is the value of Y in the trace above?

12-6-7: What is the value of Z in the trace above?

# 12.8. Try Writing a Recursive Method¶

If you would like to try writing recursive methods check out the recursion problems at CodingBat at http://codingbat.com/java/Recursion-1.