This is a step by step trace of the example presented at Tracing recursive methods.
The same trace is available with each step on its own page, starting with Step 1.
Step 1: initial call
public int mystery(int b)
{
if (b == 0)
return 0;
if (b % 2 == 0)
return mystery(b - 1) + 3; // call 1
else
return mystery(b - 1) + 2; // call 2
}
Call stack
m(5)
Explanation
Since mystery has more than one call to itself, the calls are labeled. It doesn’t matter which call is labeled call 1 and which is labeled call 2, as long as the usage is consistent.
The initial call to mystery(5) is added to the stack, abbreviated as m(5).
Step 2: mystery(5)
public int mystery(int b)
{
if (b == 0) // checks if 5 == 0, which is false
return 0;
if (b % 2 == 0) // checks if 5 is even, which is false
return mystery(b - 1) + 3; // call 1
else
return mystery(b - 1) + 2; // call 2
// stops at call 2 and calls m(4)
}
Call stack
m(4)
m(5)2
Explanation
The comments in the code above show the trace through m(5).
The statement if (b % 2 == 0) when b is 5 could be traced as: checks if 5 % 2, which is 1, is equal to 0, which is false. Since the statement is obviously checking if b is even, it could also be traced as: checks if 5 is even, which is false.
The 2 next to m(5) in the call stack indicates that m(5) stopped at call 2. This will become important when control is later returned to m(5).
The new call to m(4) is added to the top of the call stack. m(5) is suspended waiting for m(4) to return.
The + 2 is ignored because it has not yet been executed.
In the statement return mystery(b - 1) + 2;, return is the last command that executes. Everything to the right of return executes first. The return command in m(5) has not yet executed.
Step 3: mystery(4)
public int mystery(int b)
{
if (b == 0) // checks if 4 == 0, which is false
return 0;
if (b % 2 == 0) // checks if 4 is even, which is true
return mystery(b - 1) + 3; // call 1
// stops at call 1 and calls m(3)
else
return mystery(b - 1) + 2; // call 2
}
Call stack
m(3)
m(4)1
m(5)2
Explanation
The new call to m(3) is added to the top of the stack. m(4) is suspended waiting for m(3) to return. m(5) remains suspended waiting for m(4) to return. Only the topmost call on the stack that has not yet returned is active.
Step 4: mystery(3)
public int mystery(int b)
{
if (b == 0) // checks if 3 == 0, which is false
return 0;
if (b % 2 == 0) // checks if 3 is even, which is false
return mystery(b - 1) + 3; // call 1
else
return mystery(b - 1) + 2; // call 2
// stops at call 2 and calls m(2)
}
Call stack
m(2)
m(3)2
m(4)1
m(5)2
Step 5: mystery(2)
public int mystery(int b)
{
if (b == 0) // checks if 2 == 0, which is false
return 0;
if (b % 2 == 0) // checks if 2 is even, which is true
return mystery(b - 1) + 3; // call 1
// stops at call 1 and calls m(1)
else
return mystery(b - 1) + 2; // call 2
}
Call stack
m(1)
m(2)1
m(3)2
m(4)1
m(5)2
Step 6: mystery(1)
public int mystery(int b)
{
if (b == 0) // checks if 1 == 0, which is false
return 0;
if (b % 2 == 0) // checks if 1 is even, which is false
return mystery(b - 1) + 3; // call 1
else
return mystery(b - 1) + 2; // call 2
// stops at call 2 and calls m(0)
}
Call stack
m(0)
m(1)2
m(2)1
m(3)2
m(4)1
m(5)2
Step 7: mystery(0)
public int mystery(int b)
{
if (b == 0) // checks if 0 == 0, which is true
return 0; // stops and returns 0
if (b % 2 == 0)
return mystery(b - 1) + 3; // call 1
else
return mystery(b - 1) + 2; // call 2
}
Call stack
m(0) returns 0
m(1)2
m(2)1
m(3)2
m(4)1
m(5)2
Explanation
m(0) stops and returns 0. returns is added to the call stack next to m(0) to indicate that the method call has returned (ended). In this case, m(0) returns a value, so 0 is added after returns.
In a real call stack, m(0) would be removed. m(0) is left on this stack since it is difficult to remove on paper and the return value is needed for future reference.
Step 8: Back in mystery(1)
public int mystery(int b)
{
if (b == 0)
return 0;
if (b % 2 == 0)
return mystery(b - 1) + 3; // call 1
else
return mystery(b - 1) + 2; // call 2
// finished call 2, got back 0
// adds 2
// stops and returns 2
}
Call stack
m(0) returns 0
m(1) returns 2
m(2)1
m(3)2
m(4)1
m(5)2
Explanation
After m(0) returns, control returns to the topmost method on the stack that has not yet returned, which is m(1).
The stack (in the previous step) shows a 2 next to m(1), so call 2 just finished. call 2 returned 0. When a method returns a value, the return value is used in place of the method call.
The statement return mystery(b - 1) + 2;
becomes return 0 + 2;
Step 9: Back in mystery(2)
public int mystery(int b)
{
if (b == 0)
return 0;
if (b % 2 == 0)
return mystery(b - 1) + 3; // call 1
// finished call 1, got back 2
// adds 3
// stops and returns 5
else
return mystery(b - 1) + 2; // call 2
}
Call stack
m(0) returns 0
m(1) returns 2
m(2) returns 5
m(3)2
m(4)1
m(5)2
Step 10: Back in mystery(3)
public int mystery(int b)
{
if (b == 0)
return 0;
if (b % 2 == 0)
return mystery(b - 1) + 3; // call 1
else
return mystery(b - 1) + 2; // call 2
// finished call 2, got back 5
// adds 2
// stops and returns 7
}
Call stack
m(0) returns 0
m(1) returns 2
m(2) returns 5
m(3) returns 7
m(4)1
m(5)2
Step 11: Back in mystery(4)
public int mystery(int b)
{
if (b == 0)
return 0;
if (b % 2 == 0)
return mystery(b - 1) + 3; // call 1
// finished call 1, got back 7
// adds 3
// stops and returns 10
else
return mystery(b - 1) + 2; // call 2
}
Call stack
m(0) returns 0
m(1) returns 2
m(2) returns 5
m(3) returns 7
m(4) returns 10
m(5)2
Step 12: Back in mystery(5)
public int mystery(int b)
{
if (b == 0)
return 0;
if (b % 2 == 0)
return mystery(b - 1) + 3; // call 1
else
return mystery(b - 1) + 2; // call 2
// finished call 2, got back 10
// adds 2
// stops and returns 12
}
Call stack
m(0) returns 0
m(1) returns 2
m(2) returns 5
m(3) returns 7
m(4) returns 10
m(5) returns 12
Explanation
m(5) is the original call. m(5) returns 12.
Review recursive method tracing with AP CS Tutor Brandon Horn.
Additional recursion resources
- Recursive method analysis
- Recursive methods with print statements
- Recursive base conversion exercise
- DeterminantFinder exercise