Recursive Method Tracing

Question

Consider the following recursive function.

public static void mystery(int n)

{

if (n == 0 || n == 1) return;

mystery(n-2);

System.out.println(n);

mystery(n-1);

}

Write out the steps of the program in order to find the value of mystery(6).

(Hint: First figure out what mystery(2), mystery(3), and so forth print out.)

Answer 1

mystery(0) produces no output

mystery(1) produces no putput

mystery(2) outputs 2

mystery(3) outputs 3

2

mystery (4) outputs 2

4

3

2

mystery(5) outputs 3

2

5

2

4

3

2

mystery(6) outputs 2

4

3

2

6

3

2

5

2

4

3

2

Answer 2

mystery(2):

enter mystery(2)

enter mystery(0)

exit mystery(0) // does nothing

println(2)

enter mystery(1)

exit mystery(1) // does nothing

exit mystery(2) // so mystery(2) prints "2\n"

mystery(3):

enter mystery(3)

enter mystery(1)

exit mystery(1) // does nothing

println(3)

enter mystery(2)

exit mystery(2) // prints "2\n"

exit mystery(3) // so mystery(3) prints "3\n2\n"

mystery(4):

enter mystery(4)

enter mystery(2)

exit mystery(2) // prints "2\n"

println(4)

enter mystery(3)

exit mystery(3) // prints "3\n2\n"

exit mystery(4) // so mystery(4) prints "2\n4\n3\n2\n"

mystery(5):

enter mystery(5)

enter mystery(3)

exit mystery(3) // prints "3\n2\n"

println(5)

enter mystery(4)

exit mystery(4) // prints "2\n4\n3\n2\n"

exit mystery(5) // so mystery(5) prints "3\n2\n5\n2\n4\n3\n2\n"

mystery(6):

enter mystery(6)

enter mystery(4)

exit mystery(4) // prints "2\n4\n3\n2\n"

println(6)

enter mystery(5)

exit mystery(5) // prints "3\n2\n5\n2\n4\n3\n2\n"

exit mystery(6)

You can follow the pattern to figure out what mystery(6) prints.