Ітераційні та рекурсивні алгоритми Лекція з курсу Структури даних Час – 2 год

год

її допомогою можна вирішувати складні завдання чисельного аналізу, комбінаторики, алгоритмів

трансляції, операцій над списковими структурами і т.д. Програми в цьому випадку мають невеликі обсяги порівняно з ітерацією і потребують менше часу на налагодження.

спосіб завдання факторіала у вигляді
 
n! = (n-1)!  n.
 
У програмуванні

під рекурсивною процедурою (функцією) розуміють спосіб виклику процедурою (функцією) самої себе.

факторіала у вигляді   n! = 1  2  3 

4  … (n-1)  n

полягає у виділенні різних елементів, від яких залежить розв'язання, зокрема

розмірності розв'язуваної задачі. Після кожного рекурсивного виклику розмірність повинна спадати.
2. Пошук тривіального випадку та його рішення. Як правило, це ключовий етап у рекурсії, розмір-ність задачі при цьому часто дорівнює 0 або 1.
3. Декомпозиція загального випадку, що має на меті привести завдання до одного або декількох завдань того ж типу, але меншої розмірності.

на комп'ютері є його опис з використанням циклу.
Розглянемо алгоритм ітераційного

алгоритму обчислення факторіала n!.
Відповідно до визначення функції n! маємо

n!. Якщо n = 0, то змінна fctrl приймає значення

1. Якщо n ≠ 0, в циклі обчислюється добуток 1  2  3  4  … (n-1)  n. Змінна i - це параметр циклу, який послідовно приймає значення 2, 3, 4 і т.д. до n включно. Для кожного значення параметра циклу виконується тіло циклу:
 
fctrl = fctrl  i.
 

1.
Під ітерацією циклу будемо розуміти виконання тіла циклу для конкретного

значення параметра циклу.
Покрокове обчислення факторіала

визначенні полягає в тому, що визначене поняття визначається через саме

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

прогресії
 
an+1=qan, где q — коефіцієнт прогресії.
 
Рекурсивне представлення факторіала має вигляд:
 
n!

= (n-1)!  n.

всього один параметр n - ціле число.
2. Пошук тривіального випадку.

При n=0 або n=1 значення факторіала дорівнює 1, що відповідає виходу з рекурсії.
3. Декомпозиція загального випадку: n! обчислюється через меншу розмірність цієї ж задачі (n-1)!.

- структура, що містить деяку інформацію. Для цього фрейму відводиться

пам'ять і в ньому фіксуються всі значення змінних тіла функції при n=4. Відзначимо, що в рекурсивному фреймі фіксуються значення всіх змінних функції, крім глобальних.
Потім відбувається виклик Fасtоriаl(n) при n=3. Утворюється фрейм 2, де фіксуються значення змінних тіла функції при n=3.

2 відбувається звернення до Factorial(n) при n=2. В результаті цього

звернення утворюється фрейм 3, де фіксуються значення змінних тіла функції при n=2 і т.д. до тих пір, поки при черговому зверненні до функції Factorial умова n>0 не прийме значення false.
Це відбудеться в фреймі 5. У цьому фреймі отримаємо значення Factorial=1 і передамо це значення в фрейм 4.
Після цього фрейм 5 буде знищений, так як звернення Factorial(n) при n=0 буде виконано.

передамо це значення у фрейм 3, а фрейм 4 буде

закрито, оскільки звернення до Factorial(n) при n=1 буде закінчено.
Так буде згортатися ланцюжок фреймів в послідовності, зворотній тій, в якій їх породжували, поки не звернемо фрейм 1. Після цього обчислення функції буде закінчено.

звернення функції до самої себе (підкреслено у виразі), але з

меншим значенням аргументу n-1 в порівнянні з першим викликом n:
 
factorial:=factorial(n-1)  n;
 
• при обчисленні факторіала не використовується цикл, що є суттєвою особливістю рекурсивного алгоритму.

виклик з основної програми factorial(3);
2) перший рекурсивний виклик factorial(2) в

операторі
factorial:=factorial(n-1)  n,
де не відбуваються жодні обчислення - лише виклик (підкреслено);
3) другий рекурсивний виклик factorial(l);
4) отримання значення factorial(1):=1;
5) повернення з другого рекурсивного виклику і обчислення факторіала
factorial(2):= 1  2 = 2;
6) повернення з першого рекурсивного виклику і обчислення факторіала
factorial(3):= 2  3 = 6;
7) повернення в основну програму fac: = 6.

список, в якому останній вступний елемент додається до нижньої частини

списку.
Список з використанням вказівників - список, в якому кожен елемент містить вказівник на наступний елемент списку.
Однонаправлений і двонаправлений список - це лінійний список, в якому всі виключення і додавання відбуваються в будь-якому місці списку.
Однонаправлений список відрізняється від двонаправленого списку тільки зв'язком, тобто в однонаправленому списку можна переміщатися тільки в одному напрямку (з початку в кінець), а в двонаправленому - в будь-якому (рис. 2).

елемент з двонаправленого списку. При додаванні нового елементу (позначений N)

зв'язок від 3 йде до N, а від N до 4, а зв'язок між 3 і 4 видаляється.
В однонаправленому списку структура додавання і видалення така ж, тільки зв'язок між елементами односторонній.

Рис. 3. Додавання елемента в список

Рис. 4. Видалення елемента з списку

за існуючими в порядку надходження; ті дані, що надійшли першими,

при цьому обробляються першими.
Чергу іноді називають циклічною пам'яттю або списком типу FIFO («first-in-first-out» - «першим прийшов - першим обслуговується»). Іншими словами, у черзі є голова і хвіст.
У черзі новий елемент додається тільки з одного краю (рис. 5).

даному випадку це може бути тільки четвертий елемент. Черга по

суті однонаправлений список, тільки додавання і виключення елементів відбувається на кінцях списку.

робляться в одному кінці списку. Стек називають (push-down) списком, реверсивною

пам'яттю, гніздовою пам'яттю, магазином, списком типу LIFO («last-in-first-out» - «останнім прийшов - першим обслуговується"). Стек - частина пам'яті ОЗУ комп'ютера, яка призначається для тимчасового зберігання байтів, використовуваних мікропроцесором. Дії зі стеком здійснюються за допомогою регістра вказівника стека. Будь-яке пошкодження цієї частини пам'яті призводить до фатального збою.

елементів і виключення елементів - здійснюються з вершини стека, причому

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

елемента в стек покажчик спочатку переміщується «вгору» (можлива й інша

конфігурація стека, коли стек «надбудовується знизу») на довжину слоту, або комірки, а потім за значенням покажчика (індексу) в стек поміщається інформація про новий елементі. При виключенні елемента зі стека спочатку зчитується інформація про елементи, що виключаються, за значенням покажчика (індексу), а потім покажчик зміщується «вниз» (або «вгору» при зворотній конфігурації стека) на один слот. Стек вважається порожнім, якщо покажчик зміщений «вниз» на довжину однієї комірки щодо нижньої межі стека. Стек вважається повним, якщо вершина стека (покажчик стека) суміщається з верхньою межею стека.

і до стека застосована послідовність операцій: (I, I, О, I,

О, О, I, O), де символ I означає запис елемента в стек, а символ О - зчитування елемента зі стеку. Етапи виконання операцій показані на рис. 7.

всі включення і виключення робляться на обох кінцях списку (рис.

8). ще один термін «архів» застосовувався до деків з обмеженим виходом, а деки з обмеженим входом називали «переліками», або «реєстрами».

вузла йде назад до першого вузла списку (рис. 9).
В цьому

випадку можна отримати доступ до будь-якого елементу, що знаходиться в списку, вирушаючи від будь-якої заданої точки. При цьому не доводиться розрізняти в списку «останній» або «перший» вузол.

дерева.
Найбільш поширені три способи обходу вузлів дерева (рис. 10), які

отримали такі назви:
• обхід в напрямку зліва направо (зворотний порядок, інфіксний запис);
• зверху вниз (прямий порядок, префіксний запис);
• знизу вгору (кінцевий порядок, постфіксний запис).

послідовності проходження вузлів:
abcdefghi (прямий порядок);
cdbfhigea (кінцевий порядок)

виразу за допомогою бінарного дерева - рис. 12.

в зворотному і кінцевому порядках породжує відповідно послідовності:

змінюється лише порядок знаків операцій. При цьому жоден з цих

виразів не має дужок, і, таким чином, якщо не задані правила пріоритету, значення наведеного вище висловлювання на інфіксній формі не можна обчислити однозначно.

вузлів:
ABFHGIJKCDE для прямого обходу;
HFBGJIKACDE для зворотного обходу;
HFJKIGBEDCA для кінцевого обходу.