Тема 10 РЕКУРСІЯ

Питання для роздумів

1. Як Ви думаєте, як нам вдалося обмежитися пам'яттю в 10.5 кілобайт для збереження інформації про зображення в графічному вікні прикладу 2.10, якщо число пікселів у цьому вікні 22500?

2. Як Ви вважаєте, чи не можна вирішити поставлену в прикладі 2.10 задачу без використання поняття масиву?
(Відповідь: Можна. На кожному кроці першого подвійного циклу коду 2.17 можна зчитувати колір пікселя вихідного зображення за допомогою функції Point і відразу ж поміщати його в 3 точки трьох нових зображень за допомогою методу PSet.)

3. А як Ви думаєте, для яких перетворень вихідного зображення обов'язково будуть потрібні масиви, у яких зберігатимуться дані про колір кожного пікселя? (Придумайте один чи два приклади.)

3.1.Сортування трьох чисел
3.2. Рекурсивна функція і рекурсивна процедура
3.3. Сортування одномірного масиву
3.4. Сортування за допомогою Вікна списку
3.5. Приклад застосування рекурсивної процедури для створення фракталу
3.6. Додаткові відомості

Термін рекурсія дуже популярний у математиці і програмуванні. У широкому смислі, рекурсія — це звертання до самого себе (цей термін походить від латинського слова recursio — повернення). У математиці і програмуванні цей термін використовується при визначенні так званих рекурсивних функцій і рекурсивних процедур. Їх ми і будемо розглядати в даній главі.

Популярність рекурсії в програмістів у значній мірі пояснюється тим, що вона робить стиль програмування більш декларативним. Це означає, що при складанні алгоритму рішення задачі програміст іноді може схитрувати — звести рішення цієї задачі до рішення тієї ж самої задачі, але при більш простих початкових умовах. Тим самим, він як би «перекладає на плечі» комп'ютера складання дрібних деталей алгоритму. Якщо ж складання всіх навіть самих дрібних деталей алгоритму програміст залишає за собою, його стиль програмування називають не декларативним, а процедурним.

Як приклад розглянемо задачу обрахування максимального серед N чисел. У попередній главі ми розглядали алгоритм рішення цієї задачі без застосування поняття рекурсії (див. приклад 2.4 і коди 2.3 і 2.4). Можна запропонувати наступний спосіб її розв'язання:

Якщо чисел всього два, то їх треба порівняти і взяти більше.

Якщо ж чисел більше, ніж два, треба взяти кожне з них (перше, що трапилося), вирішити вихідну задачу обрахування максимального числа серед чисел, що залишилися, порівняти результат з першим числом і взяти більше.

На перший погляд у цьому рішенні є якась недомовленість — для знаходження максимального серед N чисел пропонується знайти максимальне серед N-1 числа.

Але, як це не парадоксально, представлений рекурсивний алгоритм рішення даної задачі є цілком коректним. А програма, у якій цей алгоритм реалізований, видає правильний результат.

У даній главі буде розглянуте застосування рекурсії для розв'язання різних задач, зокрема, для рішення задачі сортування одновимірного масиву — виставлення його елементів у порядку зростання (чи спадання).

Існує багато алгоритмів сортування, і ми розглянемо лише деякі з них. Зокрема, ми розповімо про так зване наївне сортування, кулькове сортування, сортування вибором і сортування виключенням.

У системі проектування Visual Basic, що Ви вивчаєте разом з вивченням мови Visual Basic, є засіб, що часто дозволяє уникнути необхідності програмувати сортування. Цим засобом є об'єкт управління, що називається Вікном списку (List Box). Розміщувані в ньому елементи (значення типу String — рядка символів) можуть автоматично впорядковуватися. Об'єкт List Box також буде розглянутий у даній главі.

А перед цим ми розглянемо одне часткове питання, зв'язане з перевіркою складних умов. Обговоривши його, ми покажемо, що без використання поняття рекурсія програмування розв'язання деяких на перший погляд простих задач може виявитися зовсім непростим.

Дата добавления: 2014-12-23