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.

about-death

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:

Asch_experiment.svg

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.

about-death

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:

about-death.png

 

 

 

 

 

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.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s