Конструктор pda і wap шпаргалок
Ітерація і рекурсія в програмуванні.
Ітерація в програмуванні
Ітерація - це організації обробки даних, при якому дії повторюються багато разів, не наводячи у своїй до викликів самих себе.
Коли якась агресивна дія необхідно повторити велику кількість разів, в програмуванні використовуються цикли. Наприклад, потрібно вивести 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);
Існує два важливих положення, відомих в математиці і в програмуванні, що визначають співвідношення між итерацией і рекурсією.
1. Будь-який ітеративний цикл може бути замінений рекурсією.
2. Рекурсія не завжди може бути замінена итерацией.
Рекурсивна схема організації обчислювального процесу
Загальна схема рекурсивного обчислювального процесу представлена на рис. 56
У блоці прийняття рішення (про продовження обчислень) проводиться перевірка є чи значення вхідних параметрів такими, для яких можливе обчислення значень вихідних параметрів відповідно до базисної частиною рекурсивного визначення. На підставі цієї перевірки приймається рішення про виконання проміжних або остаточних розрахунків. Блок проміжних обчислень можна об'єднати з блоком звернення до процедури, якщо проміжні обчислення дуже прості. У блоці остаточних розрахунків проводиться явне визначення параметрів-змінних процедури для конкретних значень вхідних параметрів, що відповідають поточній активації процедури.
В основі рекурсивного обчислювального процесу лежить рекурсивний цикл, який реалізується через виклик рекурсивної процедури, причому кожна активація рекурсивної процедури еквівалентна одному проходу ітеративного циклу While.
Загальна схема рекурсивного циклу:
if <условие цикла> then
<тело рекурсивного цикла;>
У тілі рекурсивного циклу (в блоці проміжних обчислень) обов'язково повинні міститися оператори, що змінюють значення змінних, від яких залежить умова завершення рекурсивного циклу. Нагадаємо, що виконання умови завершення рекурсивного циклу відповідає досягненню базису рекурсивного визначення. Якщо значення цих змінних не встигають змінитися до чергової активації рекурсивної процедури, виникає нескінченний рекурсивний цикл.
Загальна схема нескінченного рекурсивного циклу:
if <условие цикла> then
<тело рекурсивного цикла;>