HOME

TheInfoList



OR:

Iteration is the repetition of a process in order to generate a (possibly unbounded) sequence of outcomes. Each repetition of the process is a single iteration, and the outcome of each iteration is then the starting point of the next iteration. In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
and
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, iteration (along with the related technique of
recursion Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
) is a standard element of
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
s.


Mathematics

In mathematics, iteration may refer to the process of iterating a function, i.e. applying a function repeatedly, using the output from one iteration as the input to the next. Iteration of apparently simple functions can produce complex behaviors and difficult problems – for examples, see the
Collatz conjecture The Collatz conjecture is one of the most famous unsolved problems in mathematics. The conjecture asks whether repeating two simple arithmetic operations will eventually transform every positive integer into 1. It concerns sequences of integ ...
and
juggler sequence In number theory, a juggler sequence is an integer sequence that starts with a positive integer ''a''0, with each subsequent term in the sequence defined by the recurrence relation: a_= \begin \left \lfloor a_k^ \right \rfloor, & \text a_k \text ...
s. Another use of iteration in mathematics is in
iterative method In computational mathematics, an iterative method is a Algorithm, mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which the ''n''-th approximation is derived fr ...
s which are used to produce approximate numerical solutions to certain mathematical problems.
Newton's method In numerical analysis, Newton's method, also known as the Newton–Raphson method, named after Isaac Newton and Joseph Raphson, is a root-finding algorithm which produces successively better approximations to the roots (or zeroes) of a real-valu ...
is an example of an iterative method. Manual calculation of a number's square root is a common use and a well-known example.


Computing

In computing, iteration is the technique marking out of a block of statements within a
computer program A computer program is a sequence or set of instructions in a programming language for a computer to execute. Computer programs are one component of software, which also includes documentation and other intangible components. A computer program ...
for a defined number of repetitions. That block of statements is said to be ''iterated''; a computer scientist might also refer to that block of statements as ''an'' "iteration".


Implementations

Loops constitute the most common language constructs for performing iterations. The following
pseudocode In computer science, pseudocode is a plain language description of the steps in an algorithm or another system. Pseudocode often uses structural conventions of a normal programming language, but is intended for human reading rather than machine re ...
"iterates" three times the line of code between the curly brackets through a ''for loop'', and uses the values of ''i'' as increments. ''a'' = 0 for ''i'' from 1 to 3 // loop three times print ''a'' // the number 6 is printed (0 + 1; 1 + 2; 3 + 3) It is permissible, and often necessary, to use values from other parts of the program outside the bracketed block of statements, to perform the desired function.
Iterators In computer programming, an iterator is an object that enables a programmer to traverse a container, particularly lists. Various types of iterators are often provided via a container's interface. Though the interface and semantics of a given iterat ...
constitute alternative language constructs to loops, which ensure consistent iterations over specific data structures. They can eventually save time and effort in later coding attempts. In particular, an iterator allows one to repeat the same kind of operation at each node of such a data structure, often in some pre-defined order.
Iteratees In functional programming, an iteratee is a composability, composable Abstraction (computer science), abstraction for incrementally processing sequentially presented chunks of input data in a pure function, purely functional fashion. With iteratees, ...
are purely functional language constructs, which accept or reject data during the iterations.


Relation with recursion

Recursions and iterations have different algorithmic definitions, even though they can generate identical effects/results. The primary difference is that recursion can be employed as a solution without prior knowledge as to how many times the action will have to repeat, while a successful iteration requires that foreknowledge. Some types of programming languages, known as
functional programming language In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that m ...
s, are designed such that they do not set up block of statements for explicit repetition as with the ''for'' loop. Instead, those programming languages exclusively use
recursion Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
. Rather than call out a block of code to be repeated a pre-defined number of times, the executing code block instead "divides" the work to be done into a number separate pieces, after which the code block executes itself on each individual piece. Each piece of work will be divided repeatedly until the "amount" of work is as small as it can possibly be, at which point algorithm will do that work very quickly. The algorithm then "reverses" and reassembles the pieces into a complete whole. The classic example of recursion is in list-sorting algorithms such as
merge sort In computer science, merge sort (also commonly spelled as mergesort) is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same i ...
. The merge sort recursive algorithm will first repeatedly divide the list into consecutive pairs; each pair is then ordered, then each consecutive pair of pairs, and so forth until the elements of the list are in the desired order. The code below is an example of a recursive algorithm in the
Scheme A scheme is a systematic plan for the implementation of a certain idea. Scheme or schemer may refer to: Arts and entertainment * ''The Scheme'' (TV series), a BBC Scotland documentary series * The Scheme (band), an English pop band * ''The Schem ...
programming language that will output the same result as the pseudocode under the previous heading. (let iterate ((i 1) (a 0)) (if (<= i 3) (iterate (+ i 1) (+ a i)) (display a)))


Education

In some schools of
pedagogy Pedagogy (), most commonly understood as the approach to teaching, is the theory and practice of learning, and how this process influences, and is influenced by, the social, political and psychological development of learners. Pedagogy, taken as ...
, iterations are used to describe the process of teaching or guiding students to repeat experiments, assessments, or projects, until more accurate results are found, or the student has mastered the technical skill. This idea is found in the old adage, "Practice makes perfect." In particular, "iterative" is defined as the "process of learning and development that involves cyclical inquiry, enabling multiple opportunities for people to revisit ideas and critically reflect on their implication." Unlike computing and math, educational iterations are not predetermined; instead, the task is repeated until success according to some external criteria (often a test) is achieved.


See also

*
Recursion Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
*
Fractal In mathematics, a fractal is a geometric shape containing detailed structure at arbitrarily small scales, usually having a fractal dimension strictly exceeding the topological dimension. Many fractals appear similar at various scales, as illu ...
*
Iterated function In mathematics, an iterated function is a function (that is, a function from some set to itself) which is obtained by composing another function with itself a certain number of times. The process of repeatedly applying the same function is ...
*
Infinite compositions of analytic functions In mathematics, infinite compositions of analytic functions (ICAF) offer alternative formulations of analytic continued fractions, series, products and other infinite expansions, and the theory evolving from such compositions may shed light on the ...


References

{{reflist Articles with example pseudocode Articles with example Scheme (programming language) code Time management Fractals Programming idioms