How To Read/Trace Recursive Methods

So, recursion, one of the hardest units in APCS. The concept is pretty easy but the execution is a bit trickier. Today, I’m going to pass on a trick that my teacher taught me on how to trace your way through a recursion problem.

I’m going to assume that y’all already know what recursion is and how it works so I’ll jump straight into tracing. Let’s start off with a basic problem.

This problem is from here.

First, you have to start from the bottom of the page and go up from there. As you go through every iteration of the recursive statement, you make a new line. So, this method with an x = 5 and y = 2, if solved, would look like this:

The bottommost line contains the original call to the method with 5 and 2 being x and y, respectively. The right of the diagram shows the operations within the recursive call and all the way at the top, the 17 represents what is returned by the base case when x becomes 0.

Let’s look at a recursive method that also prints something out in each iteration of the recursive statement.

This problem is from here.

For these problems, you would have to see where the print statement is in relation to the recursive statement. If the print statement is before the recursive statement, then the order of the printed lines go up and vice versa. So the tracing would look like this if n = 3:

So the output would look like:

3

2

1

Blastoff!

If the println statement was after the recursive statement, you would have to write them next to the after arrow and Blastoff! would be printed first.

So, these are the basics. If you guys have any specific questions for specific problems, feel free to contact me and I’ll help however I can.

This is Lieutenant out.