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