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`

.

### Initial call stack

```
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`

### Resulting call stack

```
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`

### Resulting call stack

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

## Step 4: `recur(0)`

- Checks if
`0 <= 0`

, which is`true`

- Stops and returns
`1`

### Resulting call stack

```
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
```