Основні визначення
Рекурсією називається визначення об'єкта через такий же об'єкт.
В даному прикладі рекурсивної частиною визначення є "<Список> ',' <Число> ".
Зауваження 1. Рекурсивне визначення, будучи кінцевим, визначає безліч об'єктів.
Зауважимо також, що <Список> можна визначити і по-іншому:
Визначення (1) називають леворекурсівним. а (2) - праворекурсівним.
Зауваження 2. У рекурсивном визначенні обов'язково (.) Має бути присутня нерекурсівние частина.
Рекурсивне визначення може бути непрямим.
по одній з гілок рекурсивного визначення згадується об'єкт, у визначенні якого, в свою чергу, за однією з гілок визначається вихідний об'єкт.
В даному прикладі є як пряме, так і непряме рекурсивне визначення.
У програмуванні під рекурсією розуміється:
- виклик з підпрограми самої себе (пряма рекурсія)
- виклик з підпрограми іншої підпрограми, яка викликає вихідну (непряма рекурсія)
Прості приклади використання рекурсії
При виклику цієї процедури станеться рекурсивне зациклення. тому рекурсивний виклик виробляється безумовно.
Висновок. Щоб рекурсивного зациклення не відбулося, рекурсивний виклик повинен відбуватися не безумовно, а по якомусь умові, яке щоразу змінюється і при якомусь рекурсивном виклик стає хибним (так зване умова продовження рекурсії).
Виправимо нашу процедуру у відповідності зі зробленим висновком:
При виклику p (0) буде виведено:
Графічно, рекурсивні виклики можна зобразити так:
Процес послідовних рекурсивних викликів підпрограми з самої себе називається рекурсивним спуском.
Процес повернення з рекурсивних викликів називається рекурсивним поверненням.
В даному прикладі числа виводяться на рекурсивном спуску (тобто в прямому порядку).
Однак, щоб дії виконувалися в зворотному порядку, їх потрібно викликати на рекурсивном повернення.
Приклад 2. вивести
Максимальна глибина рекурсивних викликів називається глибиною рекурсії.
Поточна глибина називається поточним рівнем рекурсії.
Зауваження. Чим більше глибина рекурсії, тим більше накладні витрати по пам'яті.
Графічні зображення рекурсивних викликів
Одне графічне зображення у нас вже було. Згадаймо його:
Розглянемо більш детально виклик p (0) процедури
- Програмний стек - це безперервна область пам'яті, що виділяється програмі, зокрема, для розміщення в ній викликаються підпрограм.
- При кожному виклику підпрограми на стек кладеться її запис активації (ЗА), а при поверненні - знімається зі стека.
Т.ч. на стеку фактично зберігаються всі значення змінної i.
Зауваження 1. Оскільки при кожному рекурсивном виклик на стек поміщається ЗА, то при великій глибині рекурсії програмний стек може переповниться. і програма завершиться з помилкою.
Це станеться тим швидше, чим більше сумарний обсяг формальних параметрів і локальних змінних.
Тому наступний код - дуже поганий.
Зауваження 2. Накладні витрати на приміщення на стек ЗА, зняття ЗА зі стека, а також привласнення значень формальним параметрам на стеку досить великі.
Тому якщо є просте нерекурсівние рішення (ітераційне), то слід використовувати саме його.
Зауваження 3. Будь-яку рекурсию можна замінити итерацией.
Приклади використання рекурсії
Приклад 1. Знайти n! = N (n - 1) (n - 2). 2 * 1
Очевидно, визначити n! можемо наступним чином:
Тоді рішення має вигляд:
Однак, зауважимо, що повертається значення не визначене для n <0.
Як мінімум, можна замінити умова n = 0 на n <= 0. но, в таком случае, мы получим неверный результат, т.к. факториал вообще не определен для отрицательных чисел.
Очевидно, необхідно за допомогою затвердження перевірити коректність вхідного параметра (Assert (n> = 0)). Але його використання при кожному рекурсивном виклик накладно. Тому можна "обернути" рекурсивную підпрограму, наприклад, так:
Глибина рекурсії цього алгоритму дорівнює n.
Приклад 2. Знайти. Дамо рекурсивне визначення:
Глибина рекурсії дорівнює:
- - в кращому випадку
- - в гіршому
Приклад 3. Знаходження мінімального елемента в масиві. Визначити цей елемент можемо як мінімальний (один елемент, мінімальний з масиву без цього елемента). тобто рекурсивне визначення наступне:
Відповідно до цього маємо рішення:
Глибина рекурсії дорівнює n - 1.
Ясно, що це не дуже хороший результат.
Можна значно зменшити глибину, якщо шукати мінімальний серед приблизно рівних частин масиву. Тобто потрібно поділити масив навпіл, знайти в кожній половині мінімальні елементи і порівняти їх. Пошук в половині здійснюється подібним же чином, і розподіл проводиться до тих пір, поки в підмасиві не залишиться один елемент.
Можна ще трохи оптимізувати цей алгоритм - якщо в підмасиві два елементи, досить повернути мінімальний з них.
Тепер знання кількості елементів недостатньо: необхідно знати, серед яких елементів масиву вести пошук. Тому будемо в якості параметрів передавати ліву (l) і праву (r) кордону подмассивов.
Дамо нове рекурсивне визначення:
Глибина рекурсії такого алгоритму вже приблизно дорівнює (за кількістю ступенів).
Приклад 4. Висновок однозв'язного лінійного списку на екран.
Згадаймо, як виглядає список:
Рішення:
Глибина рекурсії дорівнює довжина списку - 1
Рекурсія називається кінцевий. якщо рекурсивний виклик є останнім в підпрограмі.
Кінцева рекурсія найбільш легко перетворюється в ітеративний алгоритм:
Доказ завершимость рекурсії
Додамо до рекурсивної процедури цілий параметр n.
Якщо при кожному рекурсивном виклик параметр n зменшується отримаємо виклики
І якщо рекурсія завершується при n <= 0. то это служит доказательством завершимости рекурсии.
Дійсно, на кожному наступному рівні рекурсії n стає менше.
Оскільки при n <= 0 рекурсивных вызовов нет, то число рекурсивных вызовов конечно.
Стверджувати, що рекурсія завершимость, можна не завжди.
Приклад.
Форми рекурсивних підпрограм
1. Дія виконується на рекурсивном спуску
2. Дія виконується на рекурсивном повернення
3. Дія виконується і на рекурсивном спуску і на рекурсивном повернення
4. Каскадна рекурсія
Ця рекурсія називається каскадної. тому кожен виклик підпрограми може породжувати кілька рекурсивних викликів (каскад).
5. Дистанційна рекурсія.
Прикладом віддаленої рекурсії служить функція Аккермана.
Приклади поганого і хорошого використання рекурсії
Приклад поганого використання рекурсії - числа Фібоначчі
Числа Фібоначчі задаються наступним рекурентним співвідношенням:
Ми вже обчислювали їх за допомогою циклів. Можливо рекурсивне (погане!) Рішення:
Ось що станеться при виклику Fib (7).
дерево рекурсивних викликів
Як бачимо, одні і ті ж числа обчислюються по кілька разів:
Алгоритм можна поліпшити, використавши масив, спочатку заповнений нулями.
При першому обчисленні fib (n) будемо заповнювати відповідний елемент, а при всіх наступних - просто звертатися до його значенню. Подібна методика називається мемоізаціей. тобто запам'ятовуванням проміжних результатів для виключення їх повторного обчислення.
Очевидно, даний спосіб вкрай неефективний в порівнянні з ітераційним алгоритмом як по пам'яті, так і за часом роботи. Зокрема, глибина рекурсії при обчисленні n-того числа Фібоначчі становить n-1.
Рекурсивний спосіб обчислення чисел Фібоначчі, побудований за ітераційного алгоритму
Нагадаємо ітераційний алгоритм пошуку n-того числа Фібоначчі:
Побудуємо за нього рекурсивний алгоритм, передаючи в кожну рекурсивную підпрограму змінні a, b, c, мінливі на кожній ітерації циклу. Фактично при кожному рекурсивном виклик ми будемо здійснювати підстановку:
Рекурсивний алгоритм, реалізований за цією підстановці, матиме вигляд:
Рекурсія в даному прикладі - кінцева. Як уже зазначалося, вона легко замінюється итерацией, при цьому як раз виходить попереднє ітераційне рішення. Хороші оптимізують компілятори роблять це автоматично.
Приклад хорошого використання рекурсії - ханойські вежі
Завдання полягає в наступному:
Дано три стрижня. На першому лежать n дисків різного радіусу за умови, що жоден диск більшого радіусу не лежить на диску менше радіуса.
Hеобходимо перенести диски з першого стрижня на третій, користуючись другим, за умови:
- за один хід можна переносити тільки один диск
- менший диск повинен лежати на більшій
Ідея алгоритму така:
Т.ч. маємо просте рекурсивне рішення:
Швидке сортування
Алгоритм швидкого сортування (різновид алгоритму «розділяй і влавствуй») складається з двох етапів:
1. Вибір деякого елемента масиву x і поділ масиву на дві частини так, що в першій виявляються всі елементи <= x, а в о второй —>= x
2. Рекурсивне застосування нашого алгоритму до отриманих частин
Очевидно, алгоритм буде працювати тим швидше, чим на більш рівні частини ми будемо ділити масив (в ідеалі - кожен раз навпіл).
Тому ми повинні прагнути вибрати елемент x так, щоб приблизно половина елементів масиву була <= его, и, соответственно, вторая половина —>=. З іншого боку, вибір x не повинен займати багато часу і, по крайней мере, не залежати від n - розміру масиву).
Ми будемо використовувати найпростіший спосіб вибору x - як нього брати перший елемент.
Наступного анімації представлений приклад застосування алгоритму швидкого сортування до масиву
Розглянемо етап 1 докладніше:
- Для поділу масиву на зазначені частини заведемо 2 індексу i і j.
- На початку i буде вказувати на перший елемент і рухатися вправо, а j - на останній і рухатися вліво.
Крок 1.
Будемо просувати i вперед до тих пір, поки A [i] не стане> = x.
Далі будемо просувати j назад до тих пір, поки A [j] не стане <= x .
Прийшли до елементів A [i] і A [j]. які "стоять не на своїх місцях" (згадаємо, що ми хочемо розкидати все менші або рівні x елементи вліво, а великі або рівні - вправо)
Крок 2.
Поміняємо їх місцями і просунемо i вперед на один елемент, а j - тому, також на один елемент.
Будемо повторювати зазначені дії до тих пір, поки i не стане> = j.
В результаті отримаємо масив A. розділений на 2 частини:
код програми
Асимптотична оцінка складності
Будемо виходити з того, що масив щоразу ділиться на 2 однакові частини. Це найкращий варіант.
Глибина рекурсії в цьому випадку = log2 n.
Т.ч. за умови поділу приблизно навпіл. асимптотична складність всього алгоритму = Θ (n log n).
Теоретично доведено, що в середньому, якщо ділимо неточно навпіл, асимптотична складність зберігає формулу Θ (n log n).
Питання: яка складність в гіршому випадку? Найгірший - коли в якості x вибираємо мінімальний (або максимальний) елемент. Це відбувається (в нашій ситуації, тому що ми вибираємо перший елемент), якщо масив вже відсортований.
В цьому випадку в результаті розбиття на частини більша частина буде зменшуватися на 1, і глибина рекурсії в процедурі Sort буде дорівнює.
Тому в гіршому випадку асимптотична складність =.
Затвердження. Для довільних даних не існує алгоритму з асимптотической складністю краще, ніж Θ (n log n) в середньому.
Генерація всіх перестановок
Основна ідея алгоритму генерації всіх перестановок полягає в наступному. У масиві довжини n, що містить перестановку, будемо міняти останній елемент з кожним, після чого будемо рекурсивно будемо робити те ж саме для масиву довжини n-1 і потім повертати переставлений елемент на старе місце. Якщо досягнута довжина масиву n = 1, то переставляти нічого не потрібно, а слід видавати вміст всього масиву-перестановки на екран. Такий алгоритм дозволить згенерувати всі перестановки, що випливає з словесного рекурсивного визначення: на останньому місці побуває кожен елемент, що міститься в даному масиві, після чого до решти масиву рекурсивно буде застосований той же алгоритм.
Неважко бачити, що глибина рекурсії становить n-1, а кількість викликів процедури Perm становить n.
Генерація всіх підмножин
Генерація всіх підмножин є алгоритм перебору. В алгоритмах перебору перебираються всі варіанти і для відповідних варіантів виконується певна дія. В даному випадку просто виводяться всі підмножини.