Some Standard Loop Problems

Now we know all of the variations on the way loops can be built, but even if you know how they can vary you will still find that there are times when it is difficult to know how best to write something. When the real world hits the theory world things aren’t always neat.

In principle it is usually easy to work out when you need a conditional or an enumeration loop by asking whether it is a condition that stops the loop or a count of the number of things to process. Similarly you can usually work out if you need a While or an Until loop – by asking whether the processing in the loop always has to be be carried out at least once or can be skipped completely. But things can be more complicated. 

The most commonly encountered problem is what do you do if what you have is what looks like an enumeration but with a "short circuit". For example, if you are searching an array for a target, once found there is no need to continue with the loop. This is usually solved with an Exit which brings the loop to a premature end:

For i = 1 To Len(array)
 	If array(i) = Target Then Exit Loop
Next i

Is this an enumeration loop or should it be rewritten as a pure conditional loop? It is very definitely a conditional loop as there is a condition which has to be met for it to end, but there is also a maximum number of times it can be carried out.

As a conditional loop it would be written something like:

i=1
Do While array[i] exists
	If array(i) = Target Then Exit Loop
	i = i+1
Loop

As you can see this is a conditional loop with two exit points. However, this isn’t the real practical problem. How do you tell if you found or didn't find the target? In other words, we have two reasons why the loop ends —either we found the target or the enumeration loop came to a natural end. There is no easy solution to this problem as it is usual for the program to do something different according to how the loop ends. So you generally need an If statement that tests to discover if the target was found. 

This is an example of a more general problem caused by any loop with multiple exit points — why has the loop terminated? Python has a nice partial solution to the problem which often simplifies the simplest case:

For w In words:
  If ( w == target) : Break
Else:  Print("Not Found")

The Else part only runs if the loop ends normally—which means it probably should be a "then" rather than an "else". Notice the Else isn't part of the If — it belongs to the loop and is only executed if the loop comes to a natural end.

There are lots of cases where what you have is really a conditional loop, but one that is also limited by a maximum number of enumerations. The real world is a bit of a mess. 

Nesting And Recursion

Loops are often nested one within another – especially enumeration loops. For example:

For i = 1 To 10
 For j = 1 To 10
  Print(i,j)
 Next j
Next i

repeats the inner loop ten times for values of i from 1 to 10. You can see that this creates 100 repeats of the Print. 

This is all very standard and very simple to any experienced programmer. What is less obvious is that loops, and nested loops in particular, are where your program soaks up time. There is a saying that you never bother optimizing any part of a program unless it is within at least two nested loops. Mind you, there is another saying that discourages any sort of optimization because it is all too difficult.

Occasionally a problem needs you to create a nest of a variable number of loops. For example, how would you to print the result of i*j for i and j from 1 to 10? This can be done with the nested loop given earlier:

For i= 1 To 10
 For j= 1 To 10
  Print(i*j)
 Next j
Next i

Now if I ask you to print i*j*k you can see that you need three nested loops. Similarly for four variables multiplied together you need four nested loops and in general for n variables multiplied together you need n nested loops.

Now consider writing this general program. It can be done. You can write a general nest of n loops but you need to make use of things like stacks to keep track of where you are. In practice most algorithms that need a variable number of nested loops are best solved using recursion, which you can read about in Chapter 10.

Recursion can implement any loop you care to think of and in this sense you always have the choice of whether to use recursion or loops. The only case where recursion makes things easier, i.e. when a recursive program is easier than a loop based program, is when there is the need for a variable number of nested loops hidden somewhere in the algorithm. 

Summary

• The basic loop is an infinite loop.

• Finite loops have exit conditions that terminate the otherwise infinite loop.

• An exit condition that has to be true to exit the loop is an Until condition.

• An exit condition that has to be false to exit the loop is a While condition.

• Loops can have any number of exit points positioned anywhere in the loop, but structured loops have a single exit point, placed either at the start or the end of the loop.

• Loops with a start exit point are generally called While loops and use a While condition. While loops can skip the body of the loop completely, i.e. they can execute the body zero or more times.

• Loops with an end exit point are generally called Until loops and use an Until condition. Until loops always execute the body of the loop at least once, i.e. they can execute the body one or more times.

• The break and continue instructions allow you to create loops that go beyond the basic While and Until loop.

• An enumeration loop is one the repeats a given number of times known before the loop starts. An enumeration loop is just a special conditional loop but still a handy construct.

• The For loop is an enumeration loop with an index counting the number of repeats.

• The C-style for loop is too general for the job it is usually assigned.

• Real life loops are often a cross between an indexed for loop and a conditional loop. 

• A common problem is knowing why a loop with multiple exit points has terminated. 

• Anything that you can do with a loop can also be done by recursion and vice versa. However, recursion is the preferred approach if you need a variable number of nested loops. 

The Trick Of The Mind - Programming & ComputationalThought

Buy Now From Amazon

Chapter List

1. The Trick Of The Mind

2. Little Languages
      Extract: Little Languages Arithmetic

3. Big Languages Are Turing Complete

4. The Strange Incident of The Goto Considered Harmful
      Extract: The Goto Considered Harmful

5. On Being Variable  

6. Representation

7. The Loop Zoo
      Extract The Loop Zoo
      Extract Advanced Loops
   

8. Modules, Subroutines, Procedures and Functions
      Extract Modular Programming

9. Top-Down Programming 

10. Algorithms
       Extract: Binary Search 
       Extract: Recursion ***NEW!!

11. The Scientific Method As Debugging 

12. The Object Of It All
       Extract Why Objects 

 <ASIN:1871962722>

<ASIN:B09MDL5J1S>

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info