Итерация – что это простыми словами. Итерация – что это простыми словами Что такое итерация в процессе

Итерация и рекурсия в программировании.

Итерация в программировании

Итерация - это организации обработки данных, при котором действия повторяются многократно, не приводя при этом к вызовам самих себя.

Когда какое-то действие необходимо повторить большое количество раз, в программировании используются циклы. Например, нужно вывести 100 раз на экран текст «Hello, World!». Вместо 100-кратного повторения одной и той же команды вывода текста часто создается цикл, который прокручивается 100 раз, и 100 раз выполняет то, что написано в теле цикла. Один шаг цикла и называется итерацией.

В программировании рекурсия - вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная рекурсия), например, функция A вызывает функцию B, а функция B - функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.

Мощь рекурсивного определения объекта в том, что такое конечное определение способно описывать бесконечно большое число объектов. С помощью рекурсивной программы же возможно описать бесконечное вычисление, причём без явных повторений частей программы.

Имеется специальный тип рекурсии, называемый «хвостовой рекурсией». Интерпретаторы и компиляторы функциональных языков программирования, поддерживающие оптимизацию кода (исходного и/или исполняемого), выполняют хвостовую рекурсию в ограниченном объёме памяти при помощи итераций.

Следует избегать избыточной глубины рекурсии, так как это может вызвать переполнение стека вызовов.

Итеративная и рекурсивная схема организации

Вычислительного процесса

Для того чтобы лучше понять особенности рекурсивных алгоритмов, полезно сопоставить итеративнную и рекурсивную огранизацию процесса вычислений в программе. Особенности итеративного и рекурсивного вычислительного процесса рассмотрим на примере вычисления значения факториала некоторого натурального числа N.

Итеративная схема организации вычислительного процесса

Итеративный процесс можно проиллюстрировать с помощью схемы, приведенной на рис. 55. Этот процесс состоит из четырех блоков: инициализации, принятия решения (о продолжении вычислений), вычисления и модификации.

В основе итеративного вычислительного процесса лежит итеративный цикл While, Repeat-Until, For. Наиболее общим является цикл While:

While < условие цикла > do < тело цикла >;

Итеративная схема вычисления факториала:

N! = 1 * 2 * 3 * … * N.

Процедура, реализующая итеративную схему вычисления факториала:

Procedure Iter_Fact (n: word; var f: word);

I:=1; f:=1; { инициализация }

While i < = n do begin { решение о завершении }

F:= f * i; { вычисления }

Inc(i); { модификация }

Существует два важных положения, известных в математике и в программировании, определяющих соотношение между итерацией и рекурсией.

1. Любой итеративный цикл может быть заменен рекурсией.

2. Рекурсия не всегда может быть заменена итерацией.

Рекурсивная схема организации вычислительного процесса

Общая схема рекурсивного вычислительного процесса представлена на рис. 56

Так как обращаться к рекурсивной процедуре можно как из нее самой, так и извне, каждое обращение к рекурсивной процедуре вызывает ее независимую активацию. При каждой активации образуются копии всех локальных переменных и формальных параметров рекурсивной процедуры, в которых “оставляют следы” операторы текущей активации. Таким образом, для рекурсивной процедуры может одновременно существовать несколько активаций. Для обеспечения правильного функционирования рекурсивной процедуры необходимо сохранять адреса возврата в таком порядке, чтобы возврат после завершения каждой текущей активации выполнялся в точку, соответствующую оператору, непосредственно следующему за оператором рекурсивного вызова. Совокупность локальных переменных, формальных параметров рекурсивной процедуры и адреса возврата однозначно характеризует текущую активацию и образует фрейм активации. Фрейм активации необходимо сохранять при очередной активации и восстанавливать после завершения текущей активации.

В блоке принятия решения (о продолжении вычислений) производится проверка, являются ли значения входных параметров такими, для которых возможно вычисление значений выходных параметров в соответствии с базисной частью рекурсивного определения. На основании этой проверки принимается решение о выполнении промежуточных или окончательных вычислений. Блок промежуточных вычислений можно объединить с блоком обращения к процедуре, если промежуточные вычисления очень просты. В блоке окончательных вычислений производится явное определение параметров-переменных процедуры для конкретных значений входных параметров, соответствующих текущей активации процедуры.

В основе рекурсивного вычислительного процесса лежит рекурсивный цикл, который реализуется через вызов рекурсивной процедуры, причем каждая активация рекурсивной процедуры эквивалентна одному проходу итеративного цикла While.

Общая схема рекурсивного цикла:

Procedure Рекурсивный_Цикл (…);

If < условие цикла > then

< тело рекурсивного цикла; >

Рекурсивный_Цикл (…);

В теле рекурсивного цикла (в блоке промежуточных вычислений) обязательно должны содержаться операторы, изменяющие значения переменных, от которых зависит условие завершения рекурсивного цикла. Напомним, что выполнение условия завершения рекурсивного цикла соответствует достижению базиса рекурсивного определения. Если значения этих переменных не успевают измениться до очередной активации рекурсивной процедуры, возникает бесконечный рекурсивный цикл.

Общая схема бесконечного рекурсивного цикла:

Procedure Бесконечный_Рекурсивный_Цикл (…);

If < условие цикла > then

Бесконечный_Рекурсивный_Цикл (…);

< тело рекурсивного цикла; >

Повторение, цикл Словарь русских синонимов. итерация сущ., кол во синонимов: 2 операция (457) … Словарь синонимов

итерация - — [] итерация Повторное применение математической операции (с измененными данными) при решении вычислительных задач для постепенного приближения к нужному результату (это видно на… … Справочник технического переводчика

Повторное применение математической операции в серии аналогичных операций, производимых для получения результата. Словарь бизнес терминов. Академик.ру. 2001 … Словарь бизнес-терминов

- (от лат. iteratio повторение) повторное применение какой либо математической операции … Большой Энциклопедический словарь

Итерация - (iteration): более чем однократное использование компонента при различном выполнении операций... Источник: ИНФОРМАЦИОННАЯ ТЕХНОЛОГИЯ. МЕТОДЫ И СРЕДСТВА ОБЕСПЕЧЕНИЯ БЕЗОПАСНОСТИ. КРИТЕРИИ ОЦЕНКИ БЕЗОПАСНОСТИ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ. ЧАСТЬ 1.… … Официальная терминология

итерация - и, ж. itération f. <лат. iterare повторять, возобновлять. мат. Результат применения какой н. математической операции, получающийся в серии аналогичных операций. Крысин 1998. Итерированный ая, ое. Повторенный. Зауэр. Лекс. СИС 1954: итера/ция … Исторический словарь галлицизмов русского языка

Итерация - повторное применение математической операции (с измененными данными) при решении вычислительных задач для постепенного приближения к нужному результату (это видно на блок схеме вычисления среднего арифметического см. рис. A.2 к статье … Экономико-математический словарь

- (лат. iteratio повторение) мат. результат применения какой л. математической операции, получающийся в серии аналогичных операций. Новый словарь иностранных слов. by EdwART, 2009. итерация [Словарь иностранных слов русского языка

- (от лат. iteratio повторение), повторное применение какой либо математической операции. * * * ИТЕРАЦИЯ ИТЕРАЦИЯ (от лат. iteratio повторение), повторное применение какой либо математической операции … Энциклопедический словарь

итерация - iteracija statusas T sritis automatika atitikmenys: angl. iteration vok. Iteration, f rus. итерация, f pranc. itération, f … Automatikos terminų žodynas

Книги

Гибкое тестирование. Практическое руководство для тестировщиков ПО и гибких команд , Криспин Лайза, Грегори Джанет. Тестирование является ключевым компонентом гибкой разработки. Широкое внедрение гибких методов привело к необходимости помещения в центр внимания приемов эффективного тестирования, а гибкие…
Нормальные семейства аналитических функций. , Монтель П.. Нормальные семейства... принадлежат перу знаменитого французского математика П. Монтеля и представляют собой монографию по теории нормальных семейств, создателемкоторой является П. Монтель, и…

Многократно повторяется слово, действие, математический знак или иероглиф. Крутится и крутится шаг в цикле программы. А иногда повторяется даже ставка на конных скачках.

Все эти разные вещи называются одним словом «итерация», которое произошло от латинского слова iteratio , что переводится как «повторяю». Слово это употребляется в совершенно различных сферах:

в математике, означая повтор той или иной математической операции или знака.
в иероглифике, означая удвоение одного символа или слога.
в программировании, где итерация может быть как и общей совокупностью операций, так и одним шагом в цикле.
в психологии итерация означает патологическое повторение действия при тяжёлых заболеваниях.
также итерация может быть выигрышной стратегией в теории игр.

Итерация в математике и программировании

Благодаря различным шуткам и познавательным изображениям гораздо более знакома людям родная сестра итерации – рекурсия. Рекурсия – это повторение объекта или процесса внутри самого себя, когда он снова и снова вызывает или повторяет себя в себе же. Итерация в этом смысле гораздо проще , ведь при повторении она никак не входит в саму себя и не обращается к своей же структуре.

В математике итерация известна не только как простое повторение символа или операции, но и как приём решения математических задач и уравнений. Существует целый большой список методов решения систем линейных алгебраических уравнений, и весь этот список является итерационным. Если говорить упрощённо, этот метод сводится к повторному решению уравнения , каждый раз находя примерный, но всё более и более близкий к правильному результат.

В программировании же итерация довольно многозначна. В большом масштабе она может означать всю структуру управления проектом. В каком-то смысле это уже не программирование, а менеджмент и организация рабочего процесса.

В данном случае итерацию можно рассматривать как полный проход по всем операциям и элементам, который приводит к выпуску продукта. Каждый отдельный случай подобного прохода-итерации в большом проекте заканчивается компилированием – сборкой итогового продукта – тестированием и возвращением к разработке.

В более мелком масштабе программирования итерация это опять-таки родная сестра рекурсии. Когда необходимо многократно ввести или вывести какие-либо данные, повторить одну и ту же операцию, в теле программы используется цикл. Один шаг такого цикла, одно исполнение заданных команд и будет итерацией.

Итерация в психиатрии

При тяжёлых расстройствах или повреждениях мозга человек может патологически и неконтролируемо выполнять какие-то действия, например, многократно и ритмично двигаться, повторять слово или часть фразы, воспроизводить жест или позу. Это повторение действий и называется итерацией, и в каком-то смысле оно близко к тиковым расстройствам.

Подобное навязчивое состояние возникает при различных болезненных состояниях : шизофрении, тяжёлом аутизме или слабоумии, при выходе из посттравматической комы, деменции, при некоторых формах клинической депрессии и многих, многих других болезнях мозга.

Итерация в психиатрии чаще всего завязана на саму себя, это повтор действий самого больного, однако иногда пациент начинает воспроизводить и повторять слова, жесты и позы окружающих его людей. Это тиковое расстройство в свою очередь называется эхопраксией, что на латинском означает «повторение действия». Отдельное же повторение слов называется эхолалией – «повторением слов».

Итерация в лингвистике

В японском языке итерация звучит гораздо более красиво – одоридзи. Одоридзи это повторение иероглифа или одного слога. Или же наоборот, избегание повтора одного и того же иероглифа, рисовать который обычно бывает трудоёмко. У этого приёма существует множество значений и способов употребления, иногда слово может даже полностью менять своё значение после удвоения иероглифа.

Однако, обычно в китайском, японском и тайском языках подобная итерация символа означает простое усиление значения , подчёркивание смысла, простое создание множественного числа или озвончение слога при его произношении. Итерация также встречалась в иероглифическом письме Древнего Египта, где она представляла из себя отдельный символ, означающий повторение предыдущего иероглифа.

Итерация в теории игр

При обычной системе игры со ставками существуют различные стратегии , ведущие к прибыли игрока, и итерация – это, наверное, самая простая из таких стратегий.

Обычно итерацией в данном случае называют повторение ставки с учётом опыта предыдущих ставок: удвоение суммы при проигрыше или же сохранение суммы ставки при выигрыше.

Итерация (лат. iteratio - повторение) - в математике, Одно из ряда повторений какой-либо математической операции, использующее результат предыдущей аналогичной операции. пример: Факториал(!) - N! = 1 х 2 х 3 x … x (N-1) x N, где N - любое целое число; Каждое последовательное умножение носит название «итерация».

Будучи существенно нелинейными вычислительными процессами, итерации в областях неустойчивости и бифуркационных «развилок» в точности воспроизводят хаотизацию поведения по сценарию Ферхюльста-Фейгенбаума, присущую нелинейным процессам самой разной физической, химической, биологической и даже социальной природы. См., напр.: Пайтген Х.-О., Рихтер П. Х. Красота фракталов. - М.: Мир, 1993.

Итерация в программировании

Итерация - это организация обработки данных, при которой действия повторяются многократно, не приводя при этом к вызовам самих себя.

Когда какое-то действие необходимо повторить большое количество раз, в программировании используются циклы . Например, нужно вывести 200 раз на экран текст «Hello, World! ». Вместо 200-кратного повторения одной и той же команды вывода текста часто создается цикл, который прокручивается 200 раз, и 200 раз выполняет то, что написано в теле цикла . Один шаг цикла и называется итерацией .

be:Ітэрацыя

Итерация представляет собой совокупность операций, в результате которой создаются выпуск продукта: стабильная исполняемая версия вместе со вспомогательными элементами, необходимыми для работы с ним. Таким образом, итерацию можно рассматривать в качестве одного полного прохода по всем дисциплинам, как минимум, включая управление требованиями, анализ и проектирование, реализация и тестирование. Итерацию можно сравнить с небольшим проектом водопадной модели. Обратите внимание на то, что критерии оценки устанавливаются отдельно для каждой итерации при ее планировании. У выпуска будет запланированный набор функций, который можно будет продемонстрировать. Продолжительность итерации зависит от масштабов и характера проекта, но в большинстве случаев в каждой итерации выполняется несколько компиляций продукта, согласно плану компоновки интеграции для конкретной итерации. Такой подход - следствие применение принципа непрерывной интеграции, рекомендованного в Rational Unified Process (RUP): по мере готовности автономно тестируемые компоненты интегрируются в систему, а затем система компонуется и тестируется на предмет правильности интеграции. При таком подходе набор функций интегрированного продукта расширяется по мере выполнения итерации и постепенно приближается к задачам, поставленным на этапе планирования итерации. Каждую компиляцию можно считать миниатюрной итерацией за той лишь разницей, что итерации требуют другого планирования и формальной оценки результатов. В некоторых проектах целесообразно компилировать продукт каждый день, однако такие компиляции нельзя назвать итерациями в определении RUP, если только это не миниатюрный проект, выполняемый одним программистом. Даже в малых проектах, над которыми работают несколько разработчиков (например, 5 программистов пишут 10000 строк кода), очень сложно реализовать итерации длительностью менее недели. Причины этого изложены в разделе Рекомендация: план разработки программного обеспечения .

Зачем нужны итерации?

Раньше большинство проектов сводилось к однократному последовательному выполнению всех предусмотренных дисциплин. Такой жизненный цикл называется водопадным :

Для такого подхода характерно накапливание огромного количества недоработок в сфере интеграции к концу цикла реализации, когда продукт впервые компилируется и начинается его тестирование. Всплывают ошибки, не замеченные на этапах анализа, проектирования и реализации, и проект практически останавливается на длительное время, в течение которого будут исправляться ошибки.

Более гибкий и менее рискованный подход к разработке заключается в многократном выполнении различных дисциплин для лучшего понимания требований, проектирования надежной архитектуры, оптимизации процесса разработки и проведения нескольких циклов реализации, в ходе которых продукт становится все более и более завершенным. Такой жизненный цикл называется итерационным . Однократное выполнение последовательности дисциплин процесса называется итерацией .

С точки зрения разработчика такой жизненный цикл представляет собой последовательность итераций , в ходе которых постепенно разрабатывается программное обеспечение. Каждая итерация заканчивается выпуском исполняемого продукта. Выпуск может поддерживать не все функции конечной системы, но при этом служит полезным источником информации для разработчиков и пользователей. Вместе с каждым выпуском создаются сопутствующие продукты работы: описание выпуска, документация, планы и т.п., а также обновленные модели системы.

Главный результат применения итерационного подхода заключается в развитии и созревании описанных ранее продуктов работы , как показано на следующей диаграмме.

Эволюция информационного наполнения на различных этапах разработки.

Малая веха

Каждая итерация завершается малой вехой, в которой проверяется соответствие результата выполнения итерации критериям оценки, установленным для данной конкретной итерации.