Backtracking Warmup

When you encounter a bug in a program, your first instinct is often to ask “Why isn’t my program doing what I want it to do?”

One of the best ways to find that answer is to instead start with a different question: “What is my program doing, and why is that different than what I intended?”

The debugger is a powerful tool for observing exactly what a program is doing. With clear information about what is happening when a program is executing, you can then tackle the next questions of how that outcome relates to what you've expressed in code and how to change the code to instead reflect your intentions.

This warmup exercise will give you practice working the debugger in the context of complex recursive problems.

Towers of Hanoi animation

You've seen the Towers of Hanoi in lecture as a classic puzzle that has a beautiful recursive solution. In this debugger exercise, we'll look at a version of the problem that also counts how many moves it takes to solve the puzzle.

The warmup.cpp includes a correct solution for the Towers of Hanoi problem along with a charming graphical animation. Run the tests in warmup.cpp to watch the animation and marvel at how that tiny recursive function is capable of doing so much. Isn’t that amazing?

Now let's dive into the debugger to see the mechanism of action behind all the recursive goodness.

1) Debugger "Step" commands

The first part of the warmup is to explore the different types of step commands in the debugger and how that relates to tracing recursive code. The controls for stepping are on the middle toolbar of the debugger view in Qt Creator. They look like this:

The five icons from left to right are the controls for Continue, Stop, Step Over, Step Into and Step Out. If you hover the mouse over an icon in Qt, a tool tip will pop up with a label to remind you of which control is which.

Set a breakpoint on the first line of the hanoiAnimation function in warmup.cpp. Run the program in Debug mode and when prompted, run the tests for warmup.cpp.

Step Over

When stopped at your breakpoint, find the yellow arrow in the left gutter that points to a numbered line of code in the editor pane. The program has stopped before this line. The upper-right pane shows the numDiscs and totalMoves variables. Because these variables have not yet been initialized, their values are unspecified; they might be 0, or they might be random garbage values.

Use Step Over to advance through each line of the hanoiAnimation function:

• Step Over the initialization of numDiscs. The Variables pane updates to show its value. The yellow arrow advances to point to the subsequent line.
• Step Over the call to HanoiGui::initialize. The execution of this function sets up the graphics window in the initial configuration and displays it.
  • If needed, move/resize your windows so that you can see both the Qt debugger and the graphics window side by side.
• Step Over the call pause and you'll note a short delay while the function is executing.
• Step Over the initialization of totalMoves and note the update in the Variables pane.
• Step Over the moveTower call and watch as the entire moveTower sequence executes and animates. That was a big step!

Step Into

Now let's practice the Step Into debugger action. Rather than stepping over function calls, Step Into goes inside the function being called so you can then step through its internal actions. If the next line to execute does not contain a function call, Step Into does the same thing as Step Over.

Restart the program and again run under in Debug mode with a breakpoint on the first line of hanoiAnimation.

• Step Into the initialization of numDiscs. Since there is no function call on the line being stepped, Step Info does the same thing as Step Over, it simply executes the single statement.
• Now Step Into to the call to HanoiGui::initialize.
  • The editor pane switches to show the contents of the hanoigui.cpp file and the yellow arrow is pointing to the first line of the initialize function. This code is unfamiliar, you didn't write it, and you didn't intend to start tracing it.
  • Step Out is your escape hatch. This "giant step" finishes the current function. When you use Step Out here, it executes all of the rest of the HanoiGUI::initialize function and control returns back to hanoiAnimation.
• Next up is the pause function, another library function you don't want to trace inside. You could step in and step out, but it's simpler to just Step Over.
• You are interested in tracing inside the moveTower function, so use Step Into to go inside. Once inside the moveTower function, Step Over each line. Control proceeds to the recursive case in the else statement. When you Step Over the recursive subcall to moveTower, the GUI window should animate moving the three-disk tower from the left peg to the middle peg. The value of totalMoves will update to count all moves made during the recursive call.

The next Step Over moves the largest disk from the left peg to the right peg. The final Step Over moves the three-disk tower from the middle to right.

Step Out

Now let's practice the Step Out debugger action. Remove any other breakpoints, and set a breakpoint inside the base case of moveTower (on the first line of code inside the if statement). Run the program in Debug mode. When stopped at your breakpoint, use Step Out.

Practice with Step Into/Over/Out

Understanding the operations of the different step actions is a great way to develop your understanding of recursion and its mechanics. Re-run the program, stop in debugger again, and do some tracing and exploration of your own. As you watch the animated discs, consider how movement relates to the sequence of recursive calls. Observe how stack frames are added and removed from the debugger call stack. When stopped, select different levels on the call stack to see the value of the parameters in the upper-right pane and the nesting of recursive calls. Here are some suggestions for when to use each kind of step:

• Step Over a recursive call is useful when thinking holistically. A recursive call is a complete "black box" that handles an entire subproblem.
• Step Into a recursive call allows you to trace the nitty-gritty details when moving from outer recursive call to inner.
• Step Out of a recursive call allows you to follow along with the action when backtracking from an inner recursive call to the outer one.

Step In, Step Over, and Step Out allow you to watch recursion work at different levels of detail. Step In lets you see what’s going on at each point in time. Step Over lets you see what a recursive function does in its entirety. Step Out lets you run the current stack frame to completion to see how the code behaves as a whole.

2) Test and debug the buggy subset sum

Your next task is to use the debugger to do what it’s designed for – to debug a program!

Forming all possible subsets of a collection uses the classic recursive pattern of include/exclude. Each node in the decision tree takes one element under consideration and branches into two recursive calls, one that includes the element and another that excludes it. The decision tree grows to a depth of N where N is the total number of elements in the collection. You have seen this in/out pattern in lecture examples to list subsets and fill a knapsack. This pattern also appears in problems such as isMeasurable and canMakeSum from the section exercises.

The warmup contains the provided countZeroSumSubset which is a correctly implemented function to explore all subsets of an input and counts those subsets whose members sum to zero. If given the input {3, 1, -3}, the enumeration of all possible subsets would be { {3, 1, -3}, {3, 1}, {3, -3}, {1, -3}, {3}, {1}, {-3}, {} }. Two of those subsets sum to zero: {3, -3} and {}, so the function return 2. Look over the implementation for countZeroSumSubsets to be sure your understand how it works before you begin debugging.

In addition to the correct implementation, there is a buggyCount version that contains a small but significant error. It’s not that far from working correctly – in fact, it comes down a difference of one character – but what difference a single character can make! Your task is to use the debugger to figure out the following:

• First, how does the observed behavior of the buggy function differ from what was expected?
• Now translate from behavior to the code: What is the function actually doing that produces that incorrect result?
• Lastly, how to change the code to correctly express the intended behavior and fix the bug.

Imagine you have just written the buggyCount version and are now going to test it. As usual, your testing plan is to add a variety of student test cases and use them to confirm that the function works correctly. When you find that inputs that do not return the correct answer, these shine the light toward where you need to debug.

Add a variety of student test cases now and use them to observe the difference between what’s produced and what’s supposed to be produced. It can be difficult to tease out the impact of the bug when you are tracing through a deep sequence of recursive calls. Try to refine your inputs down to the smallest possible input for which you can observe an error and use that as your test case. Specifically, you’re aiming to find an input where

• the output produced is wrong, and
• no shorter input produces the wrong answer

Using your minimized test case, trace the operation of countZeroSumSubsets to observe the correct behavior. Diagram the decision tree that is being traversed and match the tree to what see in the debugger as you step in/out/over. Select different stack frames in the call stack to see the state being maintained in each of the outer frames.

After completing a thorough walkthrough of the correct version, now trace buggyCount on the same input case. Watch carefully to see where in the process the bug manifests itself and how things veer off-course.

Once you have, answer the following questions by editing the short_answers.txt.

When trying to debug a recursive function, look for the simplest case where the function gives the wrong answer. Having a small test case makes it easy to reproduce the error and to trace through what’s happening in the debugger. And rather than cast wild theories about what might be going wrong, use the debugger to step and observe to see what is actually going wrong. Relate those observations to what is expressed in the code to find where to fix it to correctly reflect your intentions.

Although we are introducing these techniques in the context of debugging recursive functions, finding a minimally reproducible test case and working backward from the observed to the intention can be an effective strategy for debugging any kind of code.

Happy bug hunting!