Рекурсивні алгоритми і рекурсивні визначення
Програміст розробляє програму, зводячи вихідну задачу до більш простої. Серед цих задач може виявитися і початкова, але в спрощеній формі. Іншими словами, частиною алгоритму обчислення функції буде обчи лення цієї ж функції.
Алгоритм, що є своєю власною частиною, називається рекурсивним. Часто в основі такого алгоритму лежить рекурсивне визначення якогось поняття. Наприклад, про факторіал числа N можна сказати, що
N! = 1 * 2 *... * (N-1) * N, або 1, якщо N = 0; або ж
N! =(N-1)! *N, або 1, якщо N = 0.
Будь-яке рекурсивне визначення складається з двох частин. Одна частина визначає поняття через нього ж, інша частина - через інші поняття.
Рекурсивні процедури і функції
Записа о N = 0; або ж
N! =(N-1)! *N, або 1, якщо N = 0.
Будь-яке рекурсивне визначення складається з двох частин. Одна частина визначає поняття через нього ж, інша частина - через інші поняття.
Рекурсивні процедури і функції
Записати рекурсивний алгоритм на Паскалі можна за допомогою рекурсивної процедури. Процедура є рекурсивною, якщо вона звертається сама до себе прямо або через інші процедури.
Зауважимо, що при непрямому обертанні всі процедури в ланцюжку - рекурсивні.
Все сказане про процедури цілком відноситься і до функцій. Повернемося до рекурсивного визначення факторіала. Достатньо записати його на Паскалі й утвориться опис рекурсивної функції.
Function Factorial (N: Integer) : Integer;
Begin
< ти рекурсивний алгоритм на Паскалі можна за допомогою рекурсивної процедури. Процедура є рекурсивною, якщо вона звертається сама до себе прямо або через інші процедури.
Зауважимо, що при непрямому обертанні всі процедури в ланцюжку - рекурсивні.
Все сказане про процедури цілком відноситься і до функцій. Повернемося до рекурсивного визначення факторіала. Достатньо записати його на Паскалі й утвориться опис рекурсивної функції.
Function Factorial (N: Integer) : Integer;
Begin
If N=0 Then Factorial:=1 Else Factorial:=Factorial(N-1)*N
End;
Рекурсія зсередини
Це може здатися надзвичайним, але cамозвернення процедури нічим не відрізняється від виклику іншої процедури. Що відбувається, якщо одна процедура (або програма) викликає іншу? Загалом наступне:
1) в пам'яті розміщаються параметри, передані процедурі (але не параметри-змінні!);
2) в іншому місці пам'яті зберігаються значення внутрішніх змінних процеду ком відноситься і до функцій. Повернемося до рекурсивного визначення факторіала. Достатньо записати його на Паскалі й утвориться опис рекурсивної функції.
Function Factorial (N: Integer) : Integer;
Begin
If N=0 Then Factorial:=1 Else Factorial:=Factorial(N-1)*N
End;
Рекурсія зсередини
Це може здатися надзвичайним, але cамозвернення процедури нічим не відрізняється від виклику іншої процедури. Що відбувається, якщо одна процедура (або програма) викликає іншу? Загалом наступне:
1) в пам'яті розміщаються параметри, передані процедурі (але не параметри-змінні!);
2) в іншому місці пам'яті зберігаються значення внутрішніх змінних процедури;
3) запам'ятовується адреса повернення в процедуру;
4) керування передається викликаній процедурі.
Якщо процедуру викликати повторно з іншої процедури або ж її саму, буде виконуватися той же код, але працювати він буде з іншими значеннями параметрів і внутрішніх змінних. Це і дає можливість рекурсії.
Нехай рекурсивна процедура Stepin(X, N, Y) підносить число Х до цілого степеня N і повертає результат Y.
Procedure Stepin (X: Real; N: Integer; Var Y: Real);
Begin
If N=0 Then Y:=1 Else
Begin
Stepin(X, N-I, Y);
Y:=Y*X
End;
End;
Простежимо за станом пам'яті в процесі виконання виклику Stepin(5,3,Y). Стрілка "Þ"означає вхід у процедуру, стрілка "Ü" означає вихід із неї
|
|
|
X N
|
X’ N’
|
X” N”
|
X”’ N”’
|
Y
|
|
Þ
|
Stepin(5,3,Y)
|
5 3
|
|
|
|
?
|
|
Þ
|
Stepin(5,2,Y)
|
5 3
|
5 2
|
|
|
?
|
|
Þ
|
Stepin(5,1,Y)
|
5 3
|
5 2
|
5 1
|
|
?
|
|
Þ
|
Stepin(5,0,Y)
|
5 3
|
5 2
|
5 1
|
5 0
|
?
|
|
Ü
|
Stepin(5,0,Y)
|
5 3
|
5 2
|
5 1
|
|
1
|
|
Ü
|
Stepin(5,1,Y)
|
5 3
|
5 2
|
|
|
5
|
|
Ü
|
Stepin(5,2,Y)
|
5 3
|
|
|
|
25
|
|
Ü
|
Stepin(5,3,Y)
|
|
|
|
|
125
|
Число копій змінних, що одночасно знаходяться в пам'яті, називається глибиною рекурсії. Як видно з прикладу, спочатку вона росте, потім скорочується.
Наведемо приклад рекурсивної програми, що розв’язує відому задачу про ханойську вежу:
Program Tower;
Var
K : Integer;
Procedure Hanoy (N : Integer; One, Two, Three: Char);
Begin
If N>0 Then
Begin
Hanoy(N-1, One, Three, Two);
WriteLn(‘Перемістіть диск’,N,’зі стержня’,One,’на’,Three);
Hanoy(N-1, Two, One, Three);
End
End;
Begin
Write(‘Введіть кількість дисків’);
ReadLn(K);
Hanoy(K, ‘A’, ‘B’, ‘C’);
End.
Швидке обмінне сортування
Тепер ми готові до того, щоб познайомитися з алгоритмом сортування масиву, що у стільки раз швидше квадратичного, у скільки двійковий пошук швидше послідовного. Він має назву швидкого обмінного сортування або сортування Хоара. Нехай нам дано масив A[1]..A[N]. Рекурсивна процедура sort(L, R: integer) впорядковує частину масиву з індексами L+1,…R, не займаючи інших елементів. Далі виконується наступне:
1. Вибираємо довільний елемент масиву в якості роздільника.
2. Розташовуємо елементи масиву таким чином: менші роздільника, до ньго, а більші – після нього.
3. Сортуємо частину масиву до роздільника процедурою sort.
4. Сортуємо частину масиву після роздільника процедурою sort.
Алгоритм виконується, якщо розмір області, що сортується, більше 1. Пункт 2 можна виконати, продивляючись масив від країв до центру і міняючи місцями ключі, що порушують порядок. |
