Some Standard Loop Problems

Ok so now we know all of the variations on the way loops can be built. 

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. 

In principle it is usually easy to work out when you need a conditional or an enumeration loop - is it a condition that stops the loop or a count?

In principle you can usually work out if you need a While or an Until loop - do you want the processing in the loop to always be carried out at least once or can it 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?

Exercise for reader - rewrite as a conditional loop

The next most problem relates to the same situation. 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 test to see 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 "else". Notice the else isn't paired with the if. 

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.

If you have an array of 100 items and you are searching for a target then it is really a conditional loop because you have an exit condition but you also need to iterate though the array and the conditional loop is limited to 100 iterations at most. 

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 an old 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. 

There is also a well known historical exchange between Bob Belleville, being interviewed for a job, and Rich Williams at Apple:

Bob - "I've got lots of software experience", he declared, "in fact I've personally written over 350,000 lines of code."

When this quote was relayed to Rich he said:

"Well, I bet he did, but then he discovered loops!"

Loops and nested loops mean that a small amount of code gets run and run but there is one situation that they don't handle well. 

Occasionally a problem needs you to create a nest of a variable number of loops.

For example, if I ask 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 try and write this 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 Recursion.

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

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 much easier if you need a variable number of nested loops. 

•  Mike James is the founder and editor in chief of the I Programmer website. He is also a prolific author. Among his recent titles are The Programmer’s Guide To Theory which sets out to present the fundamental ideas of computer science in an informal and yet informative way; JavaScript Jems: The Amazing Parts and Programmer's Python: Everything is an Object. The latest is Programmer’s Guide To Kotlin, 2nd Ed.

Related Articles

Recursion 

Covariance And Contravariance - A Simple Guide

The Working Programmer's Guide To Language Paradigms

Functional And Dysfunctional Programming

Dangerous Logic - De Morgan & Programming

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

<ASIN:1871962439>

<ASIN:1871962420>

<ASIN:1871962587>

<ASIN:1871962706>