1. Розділяй і володарюй

Програма 5.4. Рекурсивна програма для обчислення префіксних виразів

Для обчислення префіксного вираження або здійснюється перетворення числа з ASCII в двійкову форму (в циклі while в кінці програми), або виконується операція, зазначена першим символом вираження, з двома операндами, які обчислюються рекурсивно. Ця функція є рекурсивної, проте використовує глобальний масив, що містить вираз і індекс поточного символу вираження. Індекс збільшується після обчислення кожного подвираженія.

char * a; int i; int eval () {int x = 0; while (a [i] == '') i ++; if (a [i] == '+') {i ++; return eval () + eval (); } If (a [i] == '*') {i ++; return eval () * eval (); } While ((a [i]> = '0') && (a [i] <= '9')) x = 10 * x + (a [i ++] -'0 '); return x; }

В принципі, будь-який цикл for можна замінити еквівалентною рекурсивної програмою. Часто рекурсивна програма надає більш природний спосіб вираження обчислення, ніж цикл for, тому можна скористатися перевагами механізму, що надається системою з підтримкою рекурсії. Однак слід пам'ятати, що тут є приховані витрати. Як повинно бути зрозуміло з прикладів, наведених на Мал. 5.3 при виконанні рекурсивної програми виклики функцій вкладаються один в інший, поки не буде досягнута точка, де замість рекурсивного виклику виконується повернення. У більшості середовищ програмування такі вкладені виклики функцій реалізуються за допомогою еквівалента вбудованих стеків. У цьому розділі ми розглянемо сутність подібного роду реалізацій. Глибина рекурсії - це максимальна ступінь вкладеності викликів функцій в ході обчислення. У загальному випадку глибина залежить від вхідних даних. Наприклад, глибина рекурсії в прикладах, наведених на Мал. 5.2 і Мал. 5.3 , Становить, відповідно, 9 і 4. бедует враховувати, що для роботи рекурсивної програми середовище програмування задіє стек, розмір якого пропорційний глибині рекурсії. При вирішенні складних завдань необхідний для цього стека обсяг пам'яті може змусити відмовитися від використання рекурсивного рішення.

Мал.5.3.

Приклад обчислення префіксного вираження

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

Огруктури даних, побудовані з вузлів з покажчиками, рекурсивні за своєю природою. Наприклад, рекурсивним є визначення зв'язкових списків в "Елементарні структури даних" (Визначення 3.3). Cледовательно, рекурсивні програми забезпечують природні реалізації для багатьох часто використовуваних функцій, що працюють з цими структурами даних. Програма 5.5 містить чотири таких прикладу. Подібні реалізації в книзі використовуються часто - в основному тому, що їх набагато простіше зрозуміти, чим їх нерекурсівние аналоги. Однак при обробці дуже великих списків рекурсивні програми, подібні програми 5.5, слід використовувати з обережністю, оскільки глибина рекурсії для таких функцій може бути пропорційна довжині списків і, відповідно, необхідний для рекурсивного стека обсяг пам'яті може виявитися занадто великим.

Деякі середовища програмування автоматично виявляють і виключають кінцеву рекурсію (tail recursion), коли останньою дією функції є рекурсія -

ний виклик, тому що в цьому випадку збільшення глибини рекурсії зовсім не обов'язково. Це удосконалення перетворило б функції підрахунку, обходу і видалення, використовувані в програмі 5.5, в цикли, але воно не може бути застосовано до функції обходу в зворотному напрямку.

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

Програма 5.5. Приклади рекурсивних функцій для зв'язкових списків

Ці рекурсивні функції для виконання простих завдань обробки списків легко записати, але вони можуть виявитися марними для дуже великих списків, оскільки глибина рекурсії може бути пропорційна довжині списку.

Перша функція, count, підраховує кількість вузлів в списку. Друга, traverse, викликає функцію visit для кожного вузла списку, з початку до кінця. Обидві функції легко реалізуються і за допомогою циклу for або while. Третя функція, traverseR, не має простого итеративного аналога. Вона викликає функцію visit для кожного вузла списку, але в зворотному порядку.

Четверта функція, remove, видаляє зі списку всі вузли з заданим значенням елемента. Реалізація цієї функції полягає в зміні посилання x = x -> next в вузлах, що передують видаляється, що можливо завдяки використанню довідкового параметра. Структурні зміни для кожної ітерації циклу while збігаються з показаними на Мал. 3.3 , Але в даному випадку і x, і t вказують на один і той же вузол.

int count (link x) {if (x == 0) return 0; return 1 + count (x -> next); } Void traverse (link h, void visit (link)) {if (h == 0) return; visit (h); traverse (h -> next, visit); } Void traverseR (link h, void visit (link)) {if (h == 0) return; traverseR (h -> next, visit); visit (h); } Void remove (link & x, Item v) {while (x! = 0 && x -> item == v) {link t = x; x = x -> next; delete t; } If (x! = 0) remove (x -> next, v); }

вправи

5.1. Напишіть рекурсивну програму для обчислення lg (N!).

5.2. Змініть програму 5.1 для обчислення N! mod M без ризику викликати переповнення. Спробуйте виконати програму для M = 997 і N = 103, 104, 105 і 106, щоб побачити, як використовувана система програмування обробляє рекурсивні виклики з великою глибиною вкладеності.

5.3. Наведіть послідовності значень аргументу, що отримуються в результаті виклику програми 5.2 для кожного з цілих чисел від 1 до 9.

5.4. Знайдіть значення N <106, при якому програма 5.2 виконує максимальну кількість рекурсивних викликів.

5.5.Создайте нерекурсівние реалізацію алгоритму Евкліда.

5.6. Наведіть малюнок, відповідний Мал. 5.2 , Для результату виконання алгоритму Евкліда з числами 89 і 55.

5.7. Визначте глибину рекурсії алгоритму Евкліда для двох послідовних чисел Фібоначчі (FN і FN + 1).

5.8. Наведіть малюнок, відповідний Мал. 5.3 , Для результату обчислення префіксного вираження + * * 12 12 12 144.

5.9. Напишіть рекурсивну програму для обчислення Постфіксний виразів.

5.10. Напишіть рекурсивну програму для обчислення інфіксне виразів, в яких операнди завжди укладені в круглі дужки.

5.11. Напишіть рекурсивну програму, яка перетворює інфіксне вираження в постфіксні.

5.12. Напишіть рекурсивну програму, яка перетворює постфіксні вираження в інфіксне.

5.13. Напишіть рекурсивну програму для вирішення завдання Йосипа Флавія (див. "Елементарні структури даних" ).

5.14. Напишіть рекурсивну програму, яка видаляє останній вузол з зв'язкового списку.

5.15. Напишіть рекурсивну програму для зміни порядку проходження вузлів в зв'язковому списку на зворотний (див. Програму 3.7). Порада: використовуйте глобальну змінну.

Розділяй і володарюй

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

Як приклад розглянемо задачу відшукання максимального з N елементів масиву a [0], ..., a [N -1]. Це завдання можна легко виконати за один прохід по масиву:

for (t = a [0], i = 1; i <N; i ++) if (a [i]> t) t = a [i];

Рекурсивне рішення типу "розділяй і володарюй", наведене в програмі 5.6 - також простий (хоча і зовсім інший) алгоритм вирішення тієї ж завдання; він приведений тільки для ілюстрації концепції "розділяй і володарюй".

Часто підхід "розділяй і володарюй" забезпечує більш швидкі рішення, ніж прості ітераційні алгоритми (в кінці розділу ми розглянемо кілька прикладів); крім того, даний підхід заслуговує уважного вивчення, бо дає змогу зрозуміти суть деяких фундаментальних обчислень.

Мал.5.4.

Рекурсивний спосіб відшукання максимуму

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

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

Як завжди, сам код пропонує перевірку правильності обчислення методом індукції:

• Він явно і негайно знаходить максимальний елемент масиву, розмір якого дорівнює 1.
• Для N> 1 код розділяє масив на два, розмір кожного з яких менше N, виходячи з індуктивного пропозиції, знаходить максимальні елементи в обох частинах і повертає більше з цих двох значень, яке повинно бути максимальним значенням для всього масиву.

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

Програма 5.6. Застосування принципу "розділяй і володарюй" для відшукання максимуму

Ця функція ділить масив a [l], ..., a [r] на масиви a [l], ..., a [m] і a [m + 1], ..., a [r], знаходить (рекурсивно) максимальні елементи в обох частинах і повертає більший з них в якості максимального елемента всього масиву. Передбачається, що Item - тип першого класу, для якого операція визначена>. Якщо розмір масиву є парним числом, обидві частини мають однакові розміри, а якщо непарних, ці розміри різняться на 1.

Item max (Item a [], int l, int r) {if (l == r) return a [l]; int m = (l + r) / 2; Item u = max (a, l, m); Item v = max (a, m + 1, r); If (u> v) return u; else return v; }

Лемма 5.1. Рекурсивна функція, яка ділить завдання розміру N на дві незалежні (непусті) частини і рекурсивно вирішує їх, викликає себе менш N раз.

Якщо одна частина має розмір до, а інша - N - k, то загальна кількість рекурсивних викликів використовуваної функції дорівнює

TN = Tk + TN - k + 1, при ; T1 = 0

Рішення TN = N - 1 можна отримати безпосередньо методом індукції. Якщо сума розмірів частин менше N, доказ того, що кількість викликів менше ніж N - 1, випливає з тих же індуктивних міркувань. Аналогічними міркуваннями можна підтвердити справедливість цього твердження і для загального випадку (див. Вправу 5.20).

Програма 5.6 - типовий приклад для багатьох алгоритмів виду "розділяй і володарюй", мають абсолютно однакову рекурсивную структуру, але інші приклади можуть відрізнятися від наведеного в двох аспектах. По-перше, програма 5.6 виконує однаковий обсяг обчислень для кожного виклику функції, і тому її загальний час виконання лінійно. Як ми побачимо, інші алгоритми "розділяй і володарюй" можуть виконувати різний обсяг обчислень для різних викликів функцій, і тому для визначення загальної тривалості виконання потрібно більш складний аналіз. Час виконання таких алгоритмів залежить від конкретного способу поділу на частини. По-друге, програма 5.6 - типовий приклад алгоритмів "розділяй і володарюй", для яких сума розмірів частин дорівнює розміру загальної задачі. Інші алгоритми "розділяй і володарюй" можуть ділити завдання на частини, сума розмірів яких менше або більше розміру початкового завдання. Ці алгоритми теж відносяться до рекурсивним алгоритмам "розділяй і володарюй", оскільки кожна частина менше цілого, але аналізувати їх важче, ніж програму 5.6. Ми детально проаналізуємо кожен з цих видів алгоритмів у міру їх розгляду.

Наприклад, алгоритм бінарного пошуку, наведений в розділі 2.6 "Принципи аналізу алгоритмів" , Є алгоритмом виду "розділяй і володарюй", який ділить завдання навпіл, а потім працює тільки з однією з цих половин. Рекурсивна реалізація бінарного пошуку буде розглянута в "Таблиці символів і дерева бінарного пошуку" .

на Мал. 5.5 показано вміст внутрішнього стека, який використовується середовищем програмування для реалізації обчислень, зображених на Мал. 5.4 . Наведена на малюнку модель є ідеалізованої, але вона дозволяє зрозуміти структуру обчислення за методом "розділяй і володарюй". Якщо в програмі є два рекурсивних виклику, то під час її виконання внутрішній стек містить спочатку один елемент, відповідний першим викликом функції під час виконання (він містить значення аргументів, локальні змінні і адреса повернення), а потім аналогічний елемент для другого виклику функції. на Мал. 5.5 показаний інший підхід - приміщення в стек відразу двох елементів зі збереженням всіх подстеков, які повинні явно створюватися в стеці. Така організація прояснює структуру обчислень і закладає основу для більш загальних обчислювальних схем, подібних до тих, про які піде мова в розділах 5.6 і 5.8.

на Мал. 5.6 показана структура алгоритму "розділяй і володарюй" для пошуку максимального значення. Ця структура є рекурсивної: верхній вузол містить розмір вхідного масиву; структура лівого подмассіва зображена зліва, а правого - справа. Формальне визначення та опис структур дерев такого виду наведені в розділах 5.4 і 5.5. Вони полегшують розуміння структури будь-яких програм, в яких використовуються вкладені виклики функцій, але особливо рекурсивних програм.

Приклад динаміки внутрішнього стека

Тут зображено ідеалізоване уявлення вмісту внутрішнього стека під час обчислення прикладу з Мал. 5.4 . Обробка починається з занесення в стек лівого і правого індексів всього подмассіва. Кожен рядок представляє результат занесення в стек двох індексів і, якщо вони не рівні, вталкивания чотирьох індексів, які обмежують лівий і правий подмасіви після поділу виштовхнутого подмассіва на дві частини. На практиці замість таких дій система зберігає в стеку адреси повернення і локальні змінні, проте ця модель цілком адекватно описує обчислення.

Рекурсивна структура алгоритму пошуку максимуму

Алгоритм "розділяй і володарюй" розбиває задачу розміром 11 на завдання з розмірами 6 і 5, завдання розміром 6 - на два завдання з розмірами 3 і 3 - і т.д., поки не буде отримана завдання розміром 1 (вгорі). Кожен гурток на цих діаграмах означає виклик рекурсивної функції для розташованих безпосередньо під нею вузлів, пов'язаних з нею лініями (квадратики означають виклики, в яких рекурсія завершується). На діаграмі в центрі показано значення індексу в середині розбиття файлу; на нижній діаграмі показано значення, що повертається.

на Мал. 5.6 внизу показано таке ж дерево, але в ньому кожен вузол містить значення, яке відповідним викликом функції. Процес створення зв'язкових структур, які представляють подібні дерева, розглядається в розділі 5.7.

Жодне розгляд рекурсії не буде повним без розгляду старовинної завдання про Ханойські вежі. Є три стержня і N дисків, які поміщаються на трьох стрижнях. Диски розрізняються розмірами і спочатку розміщуються на одному зі стрижнів від найбільшого (диск N) внизу до самого маленького (диск 1) вгорі. Завдання полягає в переміщенні дисків на сусідню позицію (стрижень) при дотриманні наступних правил: (1) одночасно можна перекласти лише один диск; і (2) жоден диск не можна покласти на диск меншого розміру. Легенда свідчить, що кінець світу настане тоді, коли якась група ченців виконає таке завдання для 40 золотих дисків на трьох алмазних стрижнях.

Програма 5.7 надає рекурсивне рішення цього завдання. Вона вказує диск, який повинен бути переміщений на кожному кроці, і напрямок його переміщення (+ означає переміщення на один стрижень вправо, або на крайній лівий, якщо поточний стрижень крайній праворуч, а - означає переміщення на один стрижень вліво, або на крайній правий, якщо поточний стрижень крайній зліва). Рекурсія заснована на наступній ідеї: для переміщення N дисків вправо на один стрижень потрібно спочатку верхні N - 1 дисків перемістити на один стрижень вліво, потім перекласти диск N на один стрижень вправо, і потім перекласти N - 1 дисків ще на один стрижень вліво (поверх диска N). Правильність цього рішення можна довести по індукції. на Мал. 5.7 показані переміщення для N = 5 і рекурсивні виклики для N = 3. Структура алгоритму досить очевидна; давайте розглянемо його детально.