Base Case Practice

A recursive method contains a call to itself. The recursion stops when a base case test is true and a value is returned.

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.

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 X

12-5-6: What is the value of X 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 = mystery()
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-5-7: What is the value of x in the trace above?

12-5-8: What is the value of y in the trace above?

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.