# 2004 AP CS AB MC #3 solution

This trace uses the technique demonstrated in tracing recursive methods and some of the material from the more complex stack based trace with nested recursive calls. Familiarity with the material from those resources is assumed, including the notation.

## Step 1: setup & initial call

There are 2 calls to recur. Label the first call 1 and the second call 2.

r(4)

## Step 2: recur(4)

• Checks if 4 <= 1, which is false
• Stops at call 1
• Calls recur with 4 - 2, which is 2

r(2)
r(4)1

## Step 3: recur(2)

• Checks if 2 <= 1, which is false
• Stops at call 1
• Calls recur with 2 - 2, which is 0

r(0)
r(2)1
r(4)1

## Step 4: recur(0)

• Checks if 0 <= 0, which is true
• Stops and returns 1

r(0)  returns 1
r(2)1
r(4)1

## Step 5: back in recur(2)

• Back in recur(2)
• Finished call 1, got back 1
• Computes 1 + ____ (something unknown)
• Stops at call 2
• Calls recur with 2 - 1, which is 1

### Resulting call stack

r(1)
r(0)  returns 1
r(2)2    1 + ____
r(4)1

## Step 6: recur(1)

• Checks if 1 <= 1, which is true
• Stops and returns 1

### Resulting call stack

r(1)  returns 1
r(0)  returns 1
r(2)2    1 + ____
r(4)1

## Step 7: back in recur(2) (again)

• Back in recur(2)
• Finished call 2, got back 1
• Computes 1 + 1, which is 2
• Stops and returns 2

### Resulting call stack

r(1)  returns 1
r(0)  returns 1
r(2)    1 + 1  returns 2
r(4)1

## Step 8: back in recur(4)

• Back in recur(4)
• Finished call 1, got back 2
• Computes 2 + ____
• Stops at call 2
• Calls recur with 4 - 1, which is 3

### Resulting call stack

r(3)
r(1)  returns 1
r(0)  returns 1
r(2)    1 + 1  returns 2
r(4)2   2 + ____

## Step 9: recur(3)

• Checks if 3 <= 1, which is false
• Stops at call 1
• Calls recur with 3 - 2, which is 1

### Resulting call stack

r(1)
r(3)1
r(1)  returns 1
r(0)  returns 1
r(2)    1 + 1  returns 2
r(4)2   2 + ____

## Step 10: recur(1)

There is no need to trace recur(1). A completed call on the stack indicates that recur(1) returns 1.

### Resulting call stack

r(1)  returns 1
r(3)1
r(1)  returns 1
r(0)  returns 1
r(2)    1 + 1  returns 2
r(4)2   2 + ____

## Step 11: back in recur(3)

• Back in recur(3)
• Finished call 1, got back 1
• Computes 1 + ____
• Stops at call 2
• Calls recur with 3 - 1, which is 2

### Resulting call stack

r(2)
r(1)  returns 1
r(3)2   1 + ____
r(1)  returns 1
r(0)  returns 1
r(2)    1 + 1  returns 2
r(4)2   2 + ____

## Step 12: recur(2)

There is no need to trace recur(2). A completed call on the stack indicates that recur(2) returns 2.

### Resulting call stack

r(2)  returns 2
r(1)  returns 1
r(3)2   1 + ____
r(1)  returns 1
r(0)  returns 1
r(2)    1 + 1  returns 2
r(4)2   2 + ____

## Step 13: back in recur(3) (again)

• Back in recur(3)
• Finished call 2, got back 2
• Computes 1 + 2, which is 3
• Stops and returns 3

### Resulting call stack

r(2)  returns 2
r(1)  returns 1
r(3)    1 + 2  returns 3
r(1)  returns 1
r(0)  returns 1
r(2)    1 + 1  returns 2
r(4)2   2 + ____

## Step 14: back in recur(4) (again)

• Back in recur(4)
• Finished call 2, got back 3
• Computes 2 + 3, which is 5
• Stops and returns 5

### Resulting call stack

r(2)  returns 2
r(1)  returns 1
r(3)    1 + 2  returns 3
r(1)  returns 1
r(0)  returns 1
r(2)    1 + 1  returns 2
r(4)    2 + 3  returns 5