How to Reason About Your Code With a Tracing Table

How to Reason About Your Code With a Tracing Table Featured Image

If you’ve spent any time in a STEM field, you’ve hopefully learned the power of drawing pictures. From free-body diagrams to chemical formulas, being able to draw a good picture will always help you solve problems. In the world of computer science, we have our own set of drawing tools. We often call them tracing tables, and they help us reason about our code.

Table of Contents

How to Make Sense of Code

As someone who codes regularly, I might be able to get a feel for what a chunk of code does at a glance. That’s because code tends to exhibit recognizable patterns that can be identified by someone with more experience.

If, however, you’re new to coding, you might not have those pattern recognition skills fleshed out yet. For you, the general approach to making sense of code is to read it line-by-line. But the question becomes, what exactly should you be doing on each line that helps you make sense of the code? My advice: track program state.

The process of tracking state can be done in many ways, but the typical strategy is to write down all of your variables and change them as they’re updated. In this article, I’ll show you a nice strategy for doing that.

Making a Tracing Table

A tracing table is a tool that is best used on programming languages that work with state (i.e., imperative programming languages). Luckily, the vast majority of popular programming languages operate this way (e.g., Java, Python, C++, etc). The reason we want a programming language that maintains state is that tables allow us to represent changes in state over time. Let me show you an example:

StatementState
int x = 0
x = 0

In this table, we have a program that has a single line of code: int x = 0. After this line is executed, we know the program state has changed: we have introduced a variable, x, that stores a value, 0. Therefore, we show that change in state in the following row of the table. This structure can be extended to any kind of code block. That said, there are a few scenarios where this structure just won’t do.

Tracing a Loop

In a previous article, I shared the following tracing table for a loop:

StatementState
int x = 0;
x = 0
int i = 1;
x = 0
i = 1
while (i < 5) {
x = 0, 1, 3, 6
i = 1, 2, 3, 4
x += i;
x = 1, 3, 6, 10
i = 1, 2, 3, 4
i++;
x = 1, 3, 6, 10
i = 2, 3, 4, 5
}
x = 10
i = 5

One thing you might notice about this tracing table is that there are multiple values on a given line. The reason for this structure is that loops can execute multiple times. Therefore, we need to show that the same value changes over time. To do that, we use commas to separate the previous value from the new one. And to make it extremely clear what the current value is, we cross out the old values.

Tracing Recursion

While loops can make tracing a bit more complicated, there are other structures as well which can throw a wrench in things like recursion. Because a new method is called with each step of recursion, we can’t rely on our listing trick from above. As a result, there are basically two ways to handle recursion: 1) create a new tracing table each time you recurse or 2) trust the recursion works.

It may seem silly, but option 2 is actually a pretty solid way of going about it. It allows you to do things like this:

StatementState
public static int factorial(int x)
x = 5
int product = factorial(x - 1) * x;
x = 5
product = 120
return product

The reason this form of tracing works is that we assume that 4! will be computed correctly (i.e., 24). Then, we can multiply 5 by the result to get 120. One of the drawbacks of this technique is that we can never know if our code actually works because we exercise all of the recursive calls. In this case, there’s actually a bug with our recursion: there’s no base case. As a result, I generally recommend starting with the smallest input first and working our way up through a technique known as confidence building (i.e., test this code for 0! then 1! then 2! and so on).

Other Ways to Trace Code

The technique described above is the way we trace loops at Ohio State. That said, as I mentioned before, tracing can be done in a variety of ways. For example, several reference recommend tracking variables only:

Other sources use similar structures to OSU, with some opting for tracking statements, variables, and program outputsOpens in a new tab.. As a result, I’d recommend looking around for a tracing structure you prefer. The exact method doesn’t matter that much.

At any rate, that’s all I wanted to cover today. Hopefully, this was useful to you! If you’d like more articles like this, let me know. In the meantime, check out some of these related articles:

And as always, if you want to go above and beyond to support the content, feel free to check out this list. There, you’ll find links to my YouTube, Discord, and Patreon. Take care!

Coding Tangents (26 Articles)—Series Navigation

As a lifelong learner and aspiring teacher, I find that not all subjects carry the same weight. As a result, some topics can fall through the cracks due to time constraints or other commitments. Personally, I find these lost artifacts to be quite fun to discuss. That’s why I’ve decided to launch a whole series to do just that. Welcome to Coding Tangents, a collection of articles that tackle the edge case topics of software development.

In this series, I’ll be tackling topics that I feel many of my own students have been curious about but never really got the chance to explore. In many cases, these are subjects that I think deserve more exposure in the classroom. For instance, did you ever receive a formal explanation of access modifiers? How about package management? Version control?

In some cases, students are forced to learn these subjects on their own. Naturally, this forms a breeding ground for misconceptions which are made popular in online forums like Stack Overflow and Reddit. With this series, I’m hoping to get back to the basics where these subjects can be tackled in their entirety.

Jeremy Grifski

Jeremy grew up in a small town where he enjoyed playing soccer and video games, practicing taekwondo, and trading Pokémon cards. Once out of the nest, he pursued a Bachelors in Computer Engineering with a minor in Game Design. After college, he spent about two years writing software for a major engineering company. Then, he earned a master's in Computer Science and Engineering. Today, he pursues a PhD in Engineering Education in order to ultimately land a teaching gig. In his spare time, Jeremy enjoys spending time with his wife, playing Overwatch and Phantasy Star Online 2, practicing trombone, watching Penguins hockey, and traveling the world.

Recent Posts