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

``````g("today", 1)
``````

## Step 2: `goAgain("today", 1)`

• Checks if `1 >= 5`, which is `false`
• Computes `"today" + ____` (something unknown)
• Calls `goAgain` with `"today".substring(1)`, which is `"oday"`, and `1 + 1`, which is `2`

### Resulting call stack

``````g("oday", 2)
g("today", 1)    "today" + ____
``````

## Step 3: `goAgain("oday", 2)`

• Checks if `2 >= 4`, which is `false`
• Computes `"oday" + ____`
• Calls `goAgain` with `"oday".substring(2)`, which is `"ay"`, and `2 + 1`, which is `3`

### Resulting call stack

``````g("ay", 3)
g("oday", 2)     "oday" + ____
g("today", 1)    "today" + ____
``````

## Step 4: `goAgain("ay", 3)`

• Checks if `3 >= 2`, which is `true`
• Stops and returns `"ay"`

### Resulting call stack

``````g("ay", 3)  returns "ay"
g("oday", 2)     "oday" + ____
g("today", 1)    "today" + ____
``````

## Step 5: Back in `goAgain("oday", 2)`

• Back in `goAgain("oday", 2)`
• Finished the recursive call, got back `"ay"`
• Computes `"oday" + "ay"`, which is `"odayay"`
• Stops and returns `"odayay"`

### Resulting call stack

``````g("ay", 3)  returns "ay"
g("oday", 2)     "oday" + "ay"  returns "odayay"
g("today", 1)    "today" + ____
``````

## Step 6: Back in `goAgain("today", 1)`

• Back in `goAgain("today", 1)`
• Finished the recursive call, got back `"odayay"`
• Computes `"today" + "odayay"`, which is `"todayodayay"`
• Stops and returns `"todayodayay"`

### Resulting call stack

``````g("ay", 3)  returns "ay"
g("oday", 2)     "oday" + "ay"  returns "odayay"
g("today", 1)    "today" + "odayay"  returns "todayodayay"
``````