This book is now obsolete Please use CSAwesome instead.

12.7. Trace Practice

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.

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

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

1mystery(4) returns 3 * mystery(3) = 3 * X = Y
2mystery(3) returns 3 * mystery(2) = 3 * 9 = 27
3mystery(2) returns 3 * mystery(1) = 3 * 3 = 9
4mystery(1) returns 3 * mystery(0) = 3 * 1 = 3
5mystery(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}

1strMethod("every") returns 1 + strMethod("very")
2strMethod("very") returns strMethod("ery")
3strMethod("ery") returns 1 + strMethod("ry")
4strMethod("ry") returns strMethod("y")
5strMethod("y") returns B

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

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

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.

You have attempted of activities on this page