Рекурсія (стор. 1 із 12)
Потрібно бути дуже терплячим,
щоб навчитися терпіння.
Не можна говорити не можна.
Корисність, важливість та необхідність рекурсії, як одного з концептуальних методів вирішення практичних завдань, підкреслювалася багатьма метрами інформатики. Пошлемося лише на двох лауреатів премії Тьюринга: американського фахівця з системного програмування Д.Кнута та англійського теоретика інформатики Ч.Хоара.
Ч. Хоару належать такі слова “Слід віддати належне генію розробників Алгола-60 за те, що вони включили у свою мову рекурсію і дали мені тим самим можливість вельми елегантно описати мій винахід (йдеться про так зване швидке сортування – Quick Sort). Уможливити витончене вираження добрих думок – я вважав це найвищою метою проекту мови програмування” [4, стор 176]. До цього слід додати, що, на сьогоднішній день, практично всі діючі мови програмування підтримують рекурсію.
У даному посібнику дається неформальне поняття рекурсії, розповідається про загальну схему вирішення задач за допомогою рекурсії та наведено рекурсивні алгоритми розв'язання дуже різноманітних за змістом та ступенем складності завдань.
1. Що таке рекурсія?
Поняття рекурсії досить просто розуміння і пов'язані з знанням будь-якого певного формалізму чи спеціальної нотації. У загальному випадку на рекурсію слід дивитися як на введення у визначення об'єкта посилання на сам об'єкт або, більш точно, як на прийом зведення розв'язання деякої задачі до вирішення “простішої” задачі такого ж класу. У програмуванні це виявляється у побудові програм (процедур і функцій), які за виконанні звертаються самі себе безпосередньо чи через ланцюжок інших програм. Здається при цих самовикликах абопослідовних циклічних викликах видимість порочного кола (circulus vitiosus – лат.) лише ілюзія. У багатьох випадках простими міркуваннями шляхом відстеження значень однієї чи кількох управляючих величин вдається провести доказ завершності обчислень за кінцеве число кроків.
Функція називається рекурсивною, якщо її визначенні міститься виклик цієї функції. Розрізняють просту рекурсію, коли текст програми функції F безпосередньо містить виклик F, і непряму рекурсію, коли F звертається до інших функцій, які містять виклик F. Тому, за текстом програми рекурсивність не завжди визначна. Знання механізмів реалізації рекурсії допомагає ефективно використовувати її. Що відбувається, коли функція F виконує рекурсивний виклик? Насамперед, запам'ятовується поточний стан програми, необхідне продовження обчислень, коли керування знову повернеться до неї. Потім F з новими значеннями аргументів починає виконуватися заново як з новим екземпляром програми. При наступному рекурсивному виклик F все повторюється і т.д. доки черговий виклик F не призводить до будь-якого тривіального випадку, що дозволяється без рекурсивних викликів. Далі, гаразд, зворотному тому, у якому запам'ятовувалась серія викликів, проводять повернення управління. У практичних додатках важливо переконатися, що максимальна глибина рекурсивних викликів не лише кінцева, а й досить мала. В іншому випадку не уникнути переповнення стека – спеціально організованої ділянки пам'яті, де запам'ятовуються окремі стани програми-функції.
У таблиці 1.1 наведено загальну схему вирішення завдань за допомогою рекурсії. Ця схема звертається сама до себе і тому є прикладом рекурсивного об'єкта. Розв'язання конкретного завдання рекурсивним методомрозпадається на кілька кроків, основними з яких є чотири етапи: параметризація, виділення бази та можливих правил її модифікації, декомпозиція та проведення відкладених обчислень. Перші три з них називають рекурсивною тріадою. У таблиці 1.1 тріада виділено загальною рамкою. Зупинимося на вказаних етапах докладніше.
Параметризація задачіполягає у виявленні сукупності вихідних величин, що визначають постановку та вирішення задачі. Значення цих параметрів чи деяких із них впливають на трудомісткість розв'язання задачі. Іноді буває корисно ввести на розгляд додаткові параметри, які безпосередньо з постановкою завдання не пов'язані, але допомагають організувати рекурсію.
Виділення бази– пошук однієї або кількох підзадач, які можуть бути вирішені безпосередньо без рекурсивного виклику.
Таблиця 1.1.Рекурсивна схема розв'язання задач за допомогою рекурсії
Якщо база змінюватиметься у процесі обчислень, має бути вказано алгоритм її зміни. Як правило, подібна динамічна база розширюється за рахунок отримання рішень проміжних завдань та полегшує виконання процесу відкладених обчислень. Можливе і звуження рекурсивної бази.
Декомпозиція загального випадкує процес послідовного розкладання вихідної задачі на серію більш простих підзадач, аналогічних вихідній задачі, кожна з яких зазвичай за тією чи іншою ознакою ближча до тривіального випадку, ніж попередня. Декомпозиція передбачає наявність деяких обчислень, що передують і сприяють переходам до більш простих завдань. Їх зручно називати попередніми обчисленнями. Декомпозицію необхідно здійснювати так, щоб нескладно було довести, що при будь-якому допустимому наборі значень параметрів рано чи пізно вонапризведе нас до одного з виділених очевидних випадків, тобто до бази.
Проведення відкладених обчислень.На останньому етапі, вирішуючи одну за одною отримані на етапі декомпозиції підзавдання в порядку зворотному їх отриманню, ми добираємося до вирішення вихідного завдання. Цей етап безпосередньо спирається на відповідні попередні обчислення (передрахунки).
Не зайве помітити, що деякі викладачі інформатики в школах та вишах мають стійку упередження проти рекурсії, неправомірно перебільшують витрати пам'яті-часу в рекурсивних алгоритмах і вважають ці витрати дуже марнотратними. Виходячи з цієї передумови, вони і діють, пропагуючи використання ітерації навіть у тих випадках, коли мають справу сутнісно з рекурсивними алгоритмами або з даними, що мають рекурсивну природу. Причини недостатньої уваги до рекурсії у поточному нормативному викладанні можна поділити на такі.
Психологічні.Відсутність диспозиційної та ситуаційної мотивацій (спонукальних причин) у більшості викладачів та їх непідготовленість як у школі, так і у вузі, до рекурсивних міркувань.
Педагогічні.Консерватизм освітнього середовища по відношенню до змісту предметної галузі;
Методичні.Відсутність усталеної робочої термінології та понятійного апарату, а також повноцінних та доступних методичних розробок за рекурсивними методами вирішення завдань.
Технічні.Недостатні ресурси швидкодії та, особливо, оперативної та дискової пам'яті навчальних комп'ютерів у недавньому минулому, а найчастіше і нині.
Технологічні.Відсутність засобів налагодження в багатьох мовах програмування та повна відсутність спеціалізованих засобів налагодження татестування рекурсивних процедур та функцій.
1. Про термінологію
У попередньому пункті, пояснюючи, що таке рекурсія, ми були змушені ввести кілька спеціальних термінів. Цей ряд потрібно продовжити. До мінімального набору, що вимагають міцного засвоєння студентами, понять і термінів слід віднести такі смислові одиниці: рекурсія, рекурсивний алгоритм, пряма рекурсія, непряма рекурсія, рекурсивні звернення, рекурентні співвідношення (поворотні послідовності), функція, що виконує, база, індикатори завершення рекурсивних викликів, простір параметрів, повна рекурсивна траєкторія, рекурсивна траекторія, рекурсивна рекурсивна рекурсивна , зріз рекурсивних обчислень, формуляр, втілення, рекурсограма, рекурсивна машина обробки формулярів, рекурсивна тавтологія, адаптивний алгоритм, візуальне мислення, рекурсивне мислення. З урахуванням пояснень деяких із цих термінів, зроблених у попередньому пункті, сенс більшої частини інших термінів ставати інтуїтивно зрозумілим. Проте дамо їм короткі пояснення (неформальні визначення). Це дозволить у подальшому уникати неточностей чи двозначностей при описі рекурсивних алгоритмів. Усі ці короткі неформальні визначення зібрані до таблиці 2.1