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

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

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

Алгоритм, що є своєю власною частиною, називається рекурсивним. Часто в основі такого алгоритму лежить рекурсивне визначення якогось поняття. Наприклад, про факторіал числа 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.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 Цивільний захист
26.09.2012 Мовнокомунікативна компетентність. Орфографічна складова
21.09.2012 OC Windows
31.05.2012 Lexikalisch-grammatischer Test. Тест для студентів 1 курсу неспеціальних факультетів.
Рекомендовані лекції
12.12.2010 Обробка графічної інформації
12.12.2010 Введення та виведення даних з використанням текстових файлів
12.12.2010 Рекурсія
12.12.2010 Порядковий тип даних
12.12.2010 Структура та синтаксис програм
12.12.2010 Алфавіт
28.09.2014 Лекції з курсу "Основи психологічної практики (практична психологія)" для студентів ІV курсу спеціальності 6.030102 Психологія
12.12.2010 ЕОМ як виконавець алгоритму. Мови програмування
22.02.2016 ОС та СП. Тема 2. Процеси та потоки. Тези
15.03.2016 ОС та СП. Тема 4. Файлові системи. Тези