|The Essence Of Loops|
|Written by Mike James|
|Thursday, 10 June 2021|
Page 4 of 4
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:
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:
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.
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:
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.
or email your comment to: email@example.com
|Last Updated ( Thursday, 10 June 2021 )|