University of Washington, AP/CS A

Lab 2: Recursion

Except where otherwise noted, the contents of this document are Copyright 2013 Stuart Reges and Marty Stepp.

lab document created by Marty Stepp, Stuart Reges and Whitaker Brand

Today's lab

Goals for this lab:

• simulate the execution of methods written using recursion
• Where you see this icon, you can click it to check the problem in Practice-It!

Exercise : Recursive Tracing (12.1)

Consider the following method.

public int mystery1(int x, int y) {
    if (x < y) {
        return x;
    } else {
        return mystery1(x - y, y);
    }
}

Fill in the boxes with the value returned by each of the method calls.

6

4

7

0

1

Exercise : Recursive Tracing (12.1)

Consider the following method.

public void mystery2(int n) {
    if (n <= 1) {
        System.out.print(n);
    } else {
        mystery2(n / 2);
        System.out.print(", " + n);
    }
}

Fill in the boxes with the output produced by each of the method calls.

1

1, 2, 4

1, 2, 4, 8, 16

1, 3, 7, 15, 30

1, 3, 6, 12, 25, 50, 100

Exercise : Recursive Tracing (12.1)

Consider the following method.

public int mystery3(int n) {
    if (n < 0) {
        return mystery3(-n);
    } else if (n < 10) {
        return n;
    } else {
        return n % 10 + mystery3(n / 10);
    }
}

Fill in the boxes with the value returned by each of the method calls.

8

11

7

10

22

Exercise : Recursive Tracing (12.1)

Consider the following method.

public void mystery4(int x, int y) {
    if (y == 1) {
        System.out.print(x);
    } else {
        System.out.print(x * y + ", ");
        mystery4(x, y - 1);
        System.out.print(", " + x * y);
    }
}

Fill in the boxes with the output produced by each of the method calls.

4

8, 4, 8

16, 8, 16

12, 8, 4, 8, 12

12, 9, 6, 3, 6, 9, 12

Exercise : Recursive Tracing (12.1)

Consider the following method.

  public void mystery5(int n) {
      if (n <= 0) {
          System.out.print("*");
      } else if (n % 2 == 0) {
          System.out.print("(");
          mystery5(n - 1);
          System.out.print(")");
      } else {
          System.out.print("[");
          mystery5(n - 1);
          System.out.print("]");
      }
  }

Fill in the boxes with the output produced by each of the method calls.

*

[*]

([*])

([([*])])

[([([*])])]