Лекції >> Програмування, комп’ютери і кібернетика >> Рекурсія

Рекурсивні алгоритми і рекурсивні визначення 

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

Алгоритм, що є своєю власною частиною, називається рекурсивним. Часто в основі такого алгоритму лежить рекурсивне визначення якогось поняття. Наприклад, про факторіал числа 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 можна виконати, продивляючись масив від країв до центру і міняючи місцями ключі, що порушують порядок.

Схожі матеріали
05.10.2012 Введення та виведення даних, розробки та опису лінійних програм.
20.12.2011 Pascal - лабораторні роботи - для студентів III-го курсу (лекції Ляшенко Б.М.)
12.12.2010 Робота з підпрограмами
12.12.2010 Робота з рядковими та символьними величинами.
12.12.2010 Робота з циклічними програмами
12.12.2010 Робота з масивами даних.
12.12.2010 Розробка та описання програм з розгалуженнями
12.12.2010 Початки програмування
12.12.2010 Етапи розв’язання задач з використанням ЕОМ
12.12.2010 Поняття про алгоритм

Тести даної категорії
12.12.2010 ПОЧАТКИ АЛГОРИТМІЗАЦІЇ. ВСТУП ДО ПРОГРАМУВАННЯ

Останні створені тести
16.03.2021 Границя, неперервність, похідна
17.04.2020 Методика проведення природознавчої розповіді з дітьми дошкільного віку
08.04.2019 Нова історія країн Азії та Африки
16.11.2015 Олімпійські ігри Стародавньої Греції. Відродження олімпійських ігор. Олімпійський рух сучасності.
28.10.2015 British Writers. Тест для студентів 4 курсу ННІ педагогіки
27.10.2015 The Passive Voice. Тест для студентів 2 курсу ННІ педагогіки
27.10.2015 Articles. Тест для студентів 1 курсу неспеціальних факультетів
27.10.2015 The Active Voice. Тест для студентів 2 курсу ННІ педагогіки
08.10.2014 INTEL
22.10.2012 Цивільний захист
Рекомендовані лекції
28.08.2020 Руйнація імперій та їх наслідки
12.12.2010 Рядки символів
12.12.2010 Константи, змінні. Типи даних
24.04.2020 Практичні методи ознайомлення дітей з природою (праця дітей у природі)
15.09.2020 Теми лекцій з ОК «Всесвітні і регіональні об’єднання та організації»
15.09.2020 Організаційна структура Європейського Союзу
23.09.2014 Котлова Л.О. Психологія конфлікту : курс лекцій
15.03.2016 ОС та СП. Тема 4. Файлові системи. Тези
05.04.2016 ОС та СП. Тема 7. Міжпроцесова та міжпотокова взаємодія. Слайди
28.08.2020 Матеріали лекційного заняття 2