This week we will finish with the fundamental concepts of programming. So far we've discussed the ideas of data structures, data types, objects, declarations, user input/output, some well-known (but simple) algorithm implementations, expressions vs. statements, and conditionals. This week we will add the concepts of iteration (loops) and recursion:
What is iteration and why do we need it? One of the things at which computers excel is performing repetitive tasks. Once you have instructed the computer with the steps needed to perform some action or solve some problem (and made sure the programming is correct of course!), the computer will happily perform that action or sequence of actions any time you ask it (by running the program). This is nowhere more apparent than in the idea of a "loop".
We have already seen a couple of loops in the algorithmic pseudocode on previous pages, although we didn't identify them as such. Remember the addition algorithm and Euclid's algorithm? Both of those sets of steps contain an instruction which says, "repeat steps n through n+m" until some condition occurs.
The idea of looping is just as fundamental to programming as the idea of conditional evaluation.
They are both critical to being able to solve problems in computing. Looping is often referred to
as "iteration", a term which generalizes the concept of doing something repeatedly,
and which emcompases all the possible implementation forms that can be used in any
programming language. For example, the C language (and lots of others) has the looping construct
'repeat-until'. FORTRAN has the 'DO loop'. Java has the 'for-each' construct (which actually
doesn't use the words "for-each") in addition to the for and while (and other) loops. C#
has the 'foreach-in' loop along with a couple of others. The point is, every language has some way
of performing the iteration task, and several have more than one way. Javascript has four: the
FOR loop, the WHILE loop, the DO-WHILE loop, and the
FOR-IN loop. Each of these versions is slightly different, as we'll soon see.
Even though your book starts the discussion of iteration with the "while" statement, the "for" loop is what most programmers think of when looping constructs are discussed, so we will start with that form. (I have no idea why this is; perhaps after this discussion you can propose some possible reasons!)
The 'for' loop has the following basic syntax:
for( var i = 0; i < 10; i++ ) {
// do some action or actions "inside" the loop
}
From this example we can see several important things. First, there are three statements inside the parentheses after the word "for". The first inside statement defines and initializes some loop counter variable so that the loop can keep track of how many iterations it has been through. We can technically start this with any value we like; we'll see this in a minute. The second of these inside statements provides the loop with a way to decide if it is done, in other words, if it has completed all the iterations it is supposed to do. Finally, the third inner statement uses the unary increment operator to add one to the value of the loop counter each time a single iteration has been performed.
The values that are in this example are NOT intended to be the only values that you can use, but in some cases showing the example with a generic syntax just mixes up the message. For this reason, I stuck in some real numbers so you could get a flavor of things. This particular loop will execute a total of ten times.
You can also see from this description how logical the idea is — it's basically a counter, which the programmer tells where to start and how many times to execute. The nice thing about this form of iteration is the way JavaScript does the loop monitoring and maintenance for you. You can define the loop variable (often called the loop counter) and initialize it. The second part is the loop "conditional" which is checked at the end of every iteration to see if it is time to stop. The third part increments the loop counter after each iteration. Here is the order in which things happen:
This particular example shown above will perform whatever code is inside the loop a total of ten
times, because the loop conditional says "i < 10". Be careful of this
— it is one of the most common programming mistakes! If you start at zero and go until 'less
than ten' that is exaclty ten iterations. If you start at 1, there will only be nine iterations!
If you start at zero but make your conditional "i <= 10" you will get
eleven iterations! This can cause confusion when using the for loop in one of its most common
applications, indexing (counting) through the elements of an array. As we've seen, the array in
JavaScript (as with many languages) starts at zero, NOT at one. You must use
care to set up the loop counter and the loop conditional correctly to avoid skipping the first
element, not going far enough to process all the elements, or going too far and "running off
the end" of the array.
The while loop does the same kind of iteration as the for loop, only you
must do the loop counter initialization and incrementing yourself in the code. Notice in the
following example, the only thing that is inside the parentheses is the loop conditional:
var index = 10;
while( index < 21 ) {
alert( "Index = " + index );
index = index + 1;
}
alert( "......and we're done!" );
WARNING! Because you must do the "maintenance" on the loop index yourself, it
is possible to end up in a situation for which either: 1) the loop won't execute at all, or 2) the
loop will never stop executing (the dreaded "endless loop" condition). Notice that there
is a line inside the loop which executes index = index + 1. This statement adds one
to the value of the index variable so that it will keep incrementing every iteration. Without this
line, the index value would remain at 10 where it was initialized, would never reach the value 21,
and the loop would never stop. In fact, the loop would not even execute our intent, since it will
just keep alerting the message, "Index = 10" over and over and over and over and over and
…! The other side of the coin involves forgetting to insure that the loop index is given an
initial value which will insure the loop executes the first time. What would happen if the value
of index was initially set to 22? Or if it was not initialized at all? Try this in a script
runner to see what happens:
var index; // Note: index is not initialized, only declared
alert( "value of index = " + index );
while( index < 21 ) {
alert( "Index = " + index );
index = index + 1;
}
alert( "......and we're done!" );
OK, quick quiz: What is the value of a declared but uninitialized variable?
The do while loop is similar, except the loop conditional is evaluated at the bottom
of the loop, after the execution of the statements contained in the body of the loop. The real
difference between the two while variants is that for a do while loop the body of the
loop is guaranteed to execute at least once. Here's an example:
var index = 10; // Note: index IS initialized
do {
alert( "Index = " + index );
index = index + 1;
} while( index < 21 );
alert( "......and we're done!" );
OBTW, you can make loops count DOWN as well as counting up, by simply making the values go the other way, and decrementing the loop counter instead of incrementing. We'll see an example in class.
One of the most common uses of a for loop is to iterate through the elements of some
collection, such as an array. For this reason, many languages, including JavaScript, have added or
included some form of for each item in <collection> perform …. The
operation of this is essentially the same as the for loop as described above, but with even more
automation added. There is no loop counter (per se), and there is no increment/decrement statement
needed. JavaScript handles all of that for you. Here's an example:
var cars = ['Chevy', 'Porsche', 'Ford', 'Ferrari', 'Tesla', 'Lotus', 'Pantera', 'Dodge', 'Cobra'];
for( var c in cars ) {
alert( "C = " + c + " and cars[c] = " + cars[c] );
}
alert( "......and we're done!" );
Notice how the variable "c" is not actually an instance of the string from the cars array, but rather takes the index of each element of the array. This is somewhat different from several other languages, such as C#, in which the variable would be each string in turn. However, with JavaScript we can easily use the variable as an index, and the rest of this loop construct is handled for us. We don't have to initialize the loop counter variable, and we don't have to keep track of when we are done or increment/decrement anything either.
Sometimes, when we are executing a loop, we may find it necessary to exit the loop before all the
iterations have been completed. For example, assume we are doing a (brute-force and inefficient)
search of an array of numbers to find a specific value. Once we have found the number for which we
are searching, there is no need to continue for the rest of the array, so we'd like to tell the
loop to stop. This is what the break statement does. The following code provides an
example (and also includes an example of the if statement to boot!):
// First let's initialize an array of random integers
// with values between 1 and 100
var rA = new Array();
for( var i = 0; i < 100; i++ ) {
rA[i] = Math.floor( 1 + Math.random() * 100 );
}
// Next, ask for a value and find it in the array
var value = prompt( "enter search number:" );
for( var i = 0; i < 100; i++ ) {
if( rA[i] == value ) {
break;
}
}
// Finally, alert the result
alert( "Found value " + value + " at element " + i );
QUICK QUIZ: Describe in your own words what this loop will do.
QUICK QUIZ: Describe in your own words what this loop will NOT do, or may not do properly.
QUICK QUIZ: Describe what happens if the loop runs to its full limit; what is the value of the loop counter? Experiment in the script runner to verify your answer.
When programming, it is important to remember the so-called Murphy's Law: "Whatever can go wrong, will go wrong." Of course, this is somewhat tongue-in-cheek, but it is a good idea to remember that as programmers we are only human and inadvertently we can introduce errors into our programs.
When a program produces incorrect, or inconsistent results, this is one kind of error, known as a logic error, which is due to incorrectly programming the algorithm. We've seen examples of this kind of error in the discussion of loops above. These errors are termed bugs and this well-known term should not be a new concept. However, there is an entirely different kind of program error which occurs when the JavaScript interpreter (and other languages as well) tries to execute a statement or expression which simply cannot be executed. When this occurs, the script cannot continue running, so it does something which is actually quite graceful: it throws an exception and stops execution.
OBTW, you may not consider this situation, which is often known as "crashing" or as "blowing up" (or even sometimes as "barfing") as a graceful program exit, but the reality is, the JavaScript interpreter, rather than trying to do too much to gracefully exit the offending program simply stops right where it is, returns a meaningful error message of some kind, and releases all resources. Most often, this method will cause the minimal amount of harm to any other running programs (including the operating system).
There are many pre-defined exceptions in JavaScript, and most other languages have something that
is similar. The C and FORTRAN languages call them "run-time errors", for example. The
UNIX operating system has something similar called a "core dump". We're working with
JavaScript, and in this case the language officially calls them Errors. Since JavaScript
is a version of ECMAScript, which defines some standard error classes, the following standard errors
are available: Error and its subtypes EvalError, RangeError, ReferenceError, SyntaxError, TypeError,
and URIError. You should be aware that there are browser implementation issues, for example, the
code try { undefinedVariable; } gives a TypeError when using Internet
Exploder, while other browsers will give a ReferenceError.
JavaScript (and other languages) has a cool feature, though, that allows for custom errors that are
defined by the programmer. Error handling is done by using a try-catch-finally block,
like so:
try {
undefinedVariable;
}
catch( e ) {
alert( typeof(e) + "\n" + e.toString() );
}
You'll see when you run this that JavaScript throws a ReferenceError and includes a
sentence that describes the error. You can also make JavaScript throw your own custom errors:
try {
undefinedVariable;
}
catch( e ) {
throw "VariableNotDefinedError"; // produces "VariableNotDefinedError"
}
To illustrate the process, here is what I did in class on Thursday this week. We took a specific problem from the sheet of problems (which is posted here) and walked through the real software development process of making this problem work. The problem is to create the encoding function for doing a simple substitution cipher. Annotated descriptions accompany the various versions on this page.
Next week we will begin talking about another super-power of programming, which is the way to define, call, and use functions. Functions are very important to making your code useful in more than one context, in web pages and other applications.
Don't forget that your next homework is due next Thursday. Have a good weekend…