This is a step by step trace of the example presented at Stack based trace with nested recursive calls. A video of this trace is also available at that page.
The same trace is available with each step on its own page, starting with Step 1.
Step 1: initial call
public static int mystery(int value)
{
if(value <= 10)
return value * 3;
return value + mystery(mystery(value / 5));
// call2 call 1
}
Call stack
m(45)
Explanation
The inner call is labeled call 1, since it is executed first.
Step 2: mystery(45)
public static int mystery(int value)
{
if(value <= 10) // checks if 45 <= 10, which is false
return value * 3;
return value + mystery(mystery(value / 5)); // computes 45 + something unknown
// call2 call 1 stops at call 1 and calls m(9)
}
Call stack
m(9)
m(45)1 45 + ____
Explanation
The code is traced in the same order it would be executed if actually run. The code computes 45 + something unknown. something unknown is represented on the stack as ____.
Step 3: mystery(9)
public static int mystery(int value)
{
if(value <= 10) // checks if 9 <= 10, which is true
return value * 3; // computes 9 * 3, which is 27
// stops and returns 27
return value + mystery(mystery(value / 5));
// call2 call 1
}
Call stack
m(9) returns 27
m(45)1 45 + ____
Step 4: Back in mystery(45)
public static int mystery(int value)
{
if(value <= 10)
return value * 3;
return value + mystery(mystery(value / 5)); // finished call 1
// call2 call 1 got back 27
// stops at call 2 and calls m(27)
}
Call stack
m(27)
m(9) returns 27
m(45)2 45 + ____
Explanation
call 1 is the inner call. When call 1 returns 27,
the statement return value + mystery(mystery(value / 5));
becomes return 45 + mystery(27);
Step 5: mystery(27)
public static int mystery(int value)
{
if(value <= 10) // checks if 27 <= 10, which is false
return value * 3;
return value + mystery(mystery(value / 5)); // computes 27 + something unknown
// call2 call 1 stops at call 1 and calls m(5)
}
Call stack
m(5)
m(27)1 27 + ____
m(9) returns 27
m(45)2 45 + ____
Step 6: mystery(5)
public static int mystery(int value)
{
if(value <= 10) // checks if 5 <= 10, which is true
return value * 3; // computes 5 * 3, which is 15
// stops and returns 15
return value + mystery(mystery(value / 5));
// call2 call 1
}
Call stack
m(5) returns 15
m(27)1 27 + ____
m(9) returns 27
m(45)2 45 + ____
Step 7: Back in mystery(27)
public static int mystery(int value)
{
if(value <= 10)
return value * 3;
return value + mystery(mystery(value / 5)); // finished call 1
// call2 call 1 got back 15
// stops at call 2 and calls m(15)
}
Call stack
m(15)
m(5) returns 15
m(27)2 27 + ____
m(9) returns 27
m(45)2 45 + ____
Step 8: mystery(15)
public static int mystery(int value)
{
if(value <= 10) // checks if 15 <= 10, which is false
return value * 3;
return value + mystery(mystery(value / 5)); // computes 15 + something unknown
// call2 call 1 stops at call 1 and calls m(3)
}
Call stack
m(3)
m(15)1 15 + ____
m(5) returns 15
m(27)2 27 + ____
m(9) returns 27
m(45)2 45 + ____
Step 9: mystery(3)
public static int mystery(int value)
{
if(value <= 10) // checks if 3 <= 10, which is true
return value * 3; // computes 3 * 3, which is 9
// stops and returns 9
return value + mystery(mystery(value / 5));
// call2 call 1
}
Call stack
m(3) returns 9
m(15)1 15 + ____
m(5) returns 15
m(27)2 27 + ____
m(9) returns 27
m(45)2 45 + ____
Step 10: Back in mystery(15)
public static int mystery(int value)
{
if(value <= 10)
return value * 3;
return value + mystery(mystery(value / 5)); // finished call 1
// call2 call 1 got back 9
// stops at call 2 and calls m(9)
}
Call stack
m(9)
m(3) returns 9
m(15)2 15 + ____
m(5) returns 15
m(27)2 27 + ____
m(9) returns 27
m(45)2 45 + ____
Step 11: mystery(9)
Call stack
m(9) returns 27
m(3) returns 9
m(15)2 15 + ____
m(5) returns 15
m(27)2 27 + ____
m(9) returns 27
m(45)2 45 + ____
Explanation
mystery(9) has already been called. As the stack indicates, mystery(9) returns 27.
In this method, 9 is a base case. If mystery(9) is traced again, as it was in Step 3, it would quickly return 27.
Some recursive methods repeatedly call themselves with the same value. Examples of this include CodingBat Recursion-1 fibonacci and at least 1 exercise in the Barron’s AP CS A prep book. Determining that a method has already been called with a specific value can reduce repetative work.
Step 12: Back in mystery(15) (again)
public static int mystery(int value)
{
if(value <= 10)
return value * 3;
return value + mystery(mystery(value / 5)); // finished call 2
// call2 call 1 got back 27
// computes 15 + 27, which is 42
// stops and returns 42
}
Call stack
m(9) returns 27
m(3) returns 9
m(15) 15 + 27 returns 42
m(5) returns 15
m(27)2 27 + ____
m(9) returns 27
m(45)2 45 + ____
Step 13: Back in mystery(27) (again)
public static int mystery(int value)
{
if(value <= 10)
return value * 3;
return value + mystery(mystery(value / 5)); // finished call 2
// call2 call 1 got back 42
// computes 27 + 42, which is 69
// stops and returns 69
}
Call stack
m(9) returns 27
m(3) returns 9
m(15) 15 + 27 returns 42
m(5) returns 15
m(27) 27 + 42 returns 69
m(9) returns 27
m(45)2 45 + ____
Step 14: Back in mystery(45) (again)
public static int mystery(int value)
{
if(value <= 10)
return value * 3;
return value + mystery(mystery(value / 5)); // finished call 2
// call2 call 1 got back 69
// computes 45 + 69, which is 114
// stops and returns 114
}
Call stack
m(9) returns 27
m(3) returns 9
m(15) 15 + 27 returns 42
m(5) returns 15
m(27) 27 + 42 returns 69
m(9) returns 27
m(45)2 45 + 69 returns 114
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