**This is an old revision of the document!**


Iteration is the method by which a process is repeated numerous times in order to reach some sort of goal. This article will primarily focus on the use of iteration in Computer Science, though it is a useful concept in many other disciplines and facets of life.

Comparison to Recursion

In many ways, iteration is just a different way of expressing recursion, as they both accomplish the same goal of executing a specific block of code statements a specified number of times. However, iteration tends to be used by imperative programming languages since it defines a set, defined order in which the explicit steps of the iteration must be executed. Recursion follows the paradigm set forth by declarative programming in that it describes what the program should accomplish without necessarily guiding the program through how to accomplish this goal.

Speaking in extremely general terms, iteration tends to be more efficient than recursion since it minimizes the number of function calls placed upon the stack; it is not uncommon to see iterative code with O(n) complexity, compared to the “typical” O(2^n - 1) complexity of an average recursive function. Again, though, the actual efficiencies depend entirely on an individual language and implementation used in each approach.

A brief example

Consider the extremely basic Python program below:

for i in range(1,10):
    print i

This program will simply print the numbers 1 through 10. We can also express this in recursion, but we will use a language better suited for recursion here than Python (specifically, Scheme). The code is as follows:

(let iterate ((i 1) (a 0))
  (if (<= i 3)
    (iterate (+ i 1) (+ a i))
    (display a)))

Notice that the iterative version is much simpler, as this is what iteration is designed for: Incrementing some sort of “counter” variable up to a specified end point. This can be used for anything from basic counting (as shown above) to extremely complicated multithreaded programs. The concept remains the same though, and the iteration looks very similar regardless of the complexity of the code blocks contained inside.

Iterators

An iterator is an object that wraps iteration, allowing a program to traverse some sort of array-like construct. They tend to be safer or more efficient than naive “looped” iteration, and some languages (such as Java) require them for more complicated constructs.

Computing


QR Code
QR Code iteration (generated for current page)