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