# 2004 AP CS A MC #26 solution

This trace uses the technique demonstrated in tracing recursive methods. Familiarity with that material is assumed.

## Step 1: initial call

### Initial call stack

``````f(6)
``````

## Step 2: `f(6)`

• Checks if `6 <= 0`, which is `false`
• Calls `g` with `6 - 1`, which is `5`

### Resulting call stack

``````g(5)
f(6)
``````

## Step 3: `g(5)`

• Checks is `5 <= 0`, which is `false`
• Calls `f` with `5 - 1`, which is `4`

### Resulting call stack

``````f(4)
g(5)
f(6)
``````

## Step 4: `f(4)`

• Checks if `4 <= 0`, which is `false`
• Calls `g` with `4 - 1`, which is `3`

### Resulting call stack

``````g(3)
f(4)
g(5)
f(6)
``````

## Step 5: `g(3)`

• Checks if `3 <= 0`, which is `false`
• Calls `f` with `3 - 1`, which is `2`

### Resulting call stack

``````f(2)
g(3)
f(4)
g(5)
f(6)
``````

## Step 6: `f(2)`

• Checks if `2 <= 0`, which is `false`
• Calls `g` with `2 - 1`, which is `1`

### Resulting call stack

``````g(1)
f(2)
g(3)
f(4)
g(5)
f(6)
``````

## Step 7: `g(1)`

• Checks if `1 <= 0`, which is `false`
• Calls `f` with `1 - 1`, which is `0`

### Resulting call stack

``````f(0)
g(1)
f(2)
g(3)
f(4)
g(5)
f(6)
``````

## Step 8: `f(0)`

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

### Resulting call stack

``````f(0)  returns 0
g(1)
f(2)
g(3)
f(4)
g(5)
f(6)
``````

## Step 9: back in `g(1)`

• Back in `g(1)`
• Finshed the call to `f`, got back `0`
• Computes `0 + 1`, which is `1`
• Stops and returns `1`

### Resulting call stack

``````f(0)  returns 0
g(1)  returns 1
f(2)
g(3)
f(4)
g(5)
f(6)
``````

## Step 10: back in `f(2)`

• Back in `f(2)`
• Finished the call to `g`, got back `1`
• Stops and returns `1`

### Resulting call stack

``````f(0)  returns 0
g(1)  returns 1
f(2)  returns 1
g(3)
f(4)
g(5)
f(6)
``````

## Step 11: back in `g(3)`

• Back in `g(3)`
• Finished the call to `f`, got back `1`
• Computes `1 + 3`, which is `4`
• Stops and returns `4`

### Resulting call stack

``````f(0)  returns 0
g(1)  returns 1
f(2)  returns 1
g(3)  returns 4
f(4)
g(5)
f(6)
``````

## Step 12: back in `f(4)`

• Back in `f(4)`
• Finished the call to `g`, got back `4`
• Stops and returns `4`

### Resulting call stack

``````f(0)  returns 0
g(1)  returns 1
f(2)  returns 1
g(3)  returns 4
f(4)  returns 4
g(5)
f(6)
``````

## Step 13: back in `g(5)`

• Back in `g(5)`
• Finished the call to `f`, got back `4`
• Computes `4 + 5`, which is `9`
• Stops and returns `9`

### Resulting call stack

``````f(0)  returns 0
g(1)  returns 1
f(2)  returns 1
g(3)  returns 4
f(4)  returns 4
g(5)  returns 9
f(6)
``````

## Step 14: back in `f(6)`

• Back in `f(6)`
• Finished the call to `g`, got back `9`
• Stop and returns `9`

### Resulting call stack

``````f(0)  returns 0
g(1)  returns 1
f(2)  returns 1
g(3)  returns 4
f(4)  returns 4
g(5)  returns 9
f(6)  returns 9
``````