Avoiding Infinite Loops

One type of infinite loop is where the sentry variable is never updated, like you just saw. But there are more insidious forms of the never-ending loop. Check out the next program. It does change the value of the sentry variable in the loop body. But something is wrong, because the loop never ends. See if you can spot the trouble before I explain what's going on.

Introducing the Losing Battle Program

The Losing Battle program describes the last, valiant fight of a hero overwhelmed by an army of trolls, a scenario you might find in a role-playing game. The program narrates the battle action. It describes the struggle, blow-by-blow, as the hero defeats a troll, but then takes more damage. In the end, the program always ends with the death of the hero. Or does it? Here's the code:

 # Losing Battle # Demonstrates the dreaded infinite loop # Michael Dawson - 1/2/03 print "Your lone hero is surrounded by a massive army of trolls." print "Their decaying green bodies stretch out, melting into the horizon." print "Your hero unsheathes his sword and begins the last fight of his life.\n" health = 10 trolls = 0 damage = 3 while health != 0:     trolls += 1     health = health - damage     print "Your hero swings and defeats an evil troll, " \            "but takes", damage, "damage points.\n" print "Your hero fought valiantly and defeated", trolls, "trolls." print "But alas, your hero is no more." raw_input("\n\nPress the enter key to exit.") 

Figure 3.9 shows a run of the program. This resulted in an infinite loop and I had to stop the process by pressing Ctrl+C, or it would have continued.

Figure 3.9: It seems you have an immortal hero. The only way to end the program was to stop the process.

So, what's going on?

Tracing the Program

Well, it looks like the program has a logical error. A good way to track down this kind of error is to trace your program's execution. Tracing means you simulate the running of your program and do exactly what it would do, following every command and keeping track of the values assigned to variables. This way, you can step through the program, understand exactly what is happening at each point, and discover the circumstances that conspire to produce the bug in your code.

The most basic way to trace a program is with old-fashioned pencil and paper. I created columns, one for each variable and condition. So to start, my page looks like this:

health

trolls

damage

health != 0

Right after the condition of the while structure is evaluated, my page looks like this:

health	trolls	damage	health != 0
10	0	3	true

Since the condition is true, the loop executes for the first time. After one full time through and back up to evaluate the condition again, my trace looks like this:

health	trolls	damage	health != 0
10	0	3	true
7	1	3	true

After a few more times through the loop, my trace looks like:

health	trolls	damage	health != 0
10	0	3	true
7	1	3	true
4	2	3	true
1	3	3	true
-2	4	3	true
-5	5	3	true
-7	6	3	true

I stopped the trace because it seemed like I was in an infinite loop. Since the value of health is negative (and not equal to 0) in the last three lines of the trace, the condition is still true. The problem is, health will never become 0. It will just grow in the negative direction each time the loop executes. As a result, the condition will never become false, and the loop will never end.

Creating Conditions That Can Become False

In addition to making sure values in a while loop's condition change, you should be sure that the condition can eventually evaluate to false; otherwise, you still have an infinite loop on your hands. In the case of the Losing Battle program, the fix is easy. The line with the condition just needs to become

 while health > 0: 

Now, if health becomes 0 or negative, the condition evaluates to false and the loop ends. To be sure, you can trace the program using this new condition:

health	trolls	damage	health > 0
10	0	3	true
7	1	3	true
4	2	3	true
1	3	3	true
-2	4	3	false

And the program ends as it should. Figure 3.10 shows how the debugged program runs.

Figure 3.10: Now, the program runs correctly, avoiding an infinite loop. Your hero's fate, however, is not as bright.