# 2009 AP CS A MC #39 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.

The same trace is available with each step on its own page, starting with Step 1.

## Step 1: initial call

### Initial call stack

``````r(32)
``````

## Step 2: `recur(32)`

• Computes `32 % 3`, which is `2`
• Computes `"" + 2`, which is `"2"`
• Creates `dig` and sets it to point to `"2"`
• Checks if `32 / 3`, which is `10` is `> 0`, which is `true`
• Computes `"2" + ___` (something unknown)
• Calls `recur` with `32 / 3`, which is `10`

### Resulting call stack

``````r(10)
r(32)    dig -> "2"    "2" + ____
``````

## Step 3: `recur(10)`

• Computes `10 % 3`, which is `1`
• Computes `"" + 1`, which is `"1"`
• Creates `dig` and sets it to point to `"1"`
• Checks if `10 / 3`, which is `3` is `> 0`, which is `true`
• Computes `"1" + ____`
• Calls `recur` with `10 / 3`, which is `3`

### Resulting call stack

``````r(3)
r(10)    dig -> "1"    "1" + ____
r(32)    dig -> "2"    "2" + ____
``````

## Step 4: `recur(3)`

• Computes `3 % 3`, which is `0`
• Computes `"" + 0`, which is `"0"`
• Creates `dig` and sets it to point to `"0"`
• Checks if `3 / 3`, which is `1` is `> 0`, which is `true`
• Computes `"0" + ____`
• Calls `recur` with `3 / 3`, which is `1`

### Resulting call stack

``````r(1)
r(3)     dig -> "0"    "0" + ____
r(10)    dig -> "1"    "1" + ____
r(32)    dig -> "2"    "2" + ____
``````

## Step 5: `recur(1)`

• Computes `1 % 3`, which is `1`
• Computes `"" + 1`, which is `"1"`
• Creates `dig` and sets it to point to `"1"`
• Checks if `1 / 3`, which is `0`, is `> 0`, which is `false`
• Stops and returns `"1"`

### Resulting call stack

``````r(1)  returns "1"
r(3)     dig -> "0"    "0" + ____
r(10)    dig -> "1"    "1" + ____
r(32)    dig -> "2"    "2" + ____
``````

## Step 6: Back in `recur(3)`

• Back in `recur(3)`
• Finished the recurusive call, got back `"1"`
• Computes `"0" + "1"`, which is `"01"`
• Stops and returns `"01"`

### Resulting call stack

``````r(1)  returns "1"
r(3)     dig -> "0"    "0" + "1"  returns "01"
r(10)    dig -> "1"    "1" + ____
r(32)    dig -> "2"    "2" + ____
``````

## Step 7: Back in `recur(10)`

• Back in `recur(10)`
• Finished the recursive call, got back `"01"`
• Computes `"1" + "01"`, which is `"101"`
• Stops and returns `"101"`

### Resulting call stack

``````r(1)  returns "1"
r(3)     dig -> "0"    "0" + "1"   returns "01"
r(10)    dig -> "1"    "1" + "01"  returns "101
r(32)    dig -> "2"    "2" + ____
``````

## Step 8: Back in `recur(32)`

• Back in `recur(32)`
• Finished the recursive call, got back `"101"`
• Computes `"2" + "101"`, which is `"2101"`
• Stops and returns `"2101"`

### Resulting call stack

``````r(1)  returns "1"
r(3)     dig -> "0"    "0" + "1"   returns "01"
r(10)    dig -> "1"    "1" + "01"  returns "101
r(32)    dig -> "2"    "2" + "101" returns "2101"
``````