10.1.6. groupwork Tracing Challenge : Recursion

Working in pairs, trace through the following recursion problems.

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.

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

10-1-14: 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.

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

10-1-15: What is the value of X in the trace above?

10-1-16: 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));
   }
}
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

10-1-17: 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.

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

10-1-18: What is the value of X in the trace above?

10-1-19: What is the value of Y in the trace above?

10-1-20: What is the value of Z in the trace above?

10.1.7. Summary

You have attempted of activities on this page
Next Section - 10.2. Recursive Searching and Sorting