Рекурсивна функція
Поняття рекурсії досить просто розуміння і пов'язані з знанням будь-якого певного формалізму чи спеціальної нотації. У загальному випадку на рекурсію слід дивитися як на введення у визначення об'єкта посилання на сам об'єкт або, більш точно, як на прийом зведення розв'язання деякої задачі до вирішення “простішої” задачі такого ж класу. У програмуванні це виявляється у побудові програм (процедур і функцій), які за виконанні звертаються самі себе безпосередньо чи через ланцюжок інших програм.
Працюючи з підпрограмами важливими є поняттяформальних і фактичних параметрів.Формальні параметри– це ідентифікатори вхідних даних для підпрограми. Якщо формальні параметри набувають конкретних значень, то вони називаютьсяфактичними. Формальні параметри можуть отримати конкретні значення тільки в тій програмі, де здійснюється звернення до цього модуля-підпрограми.Тип тапорядок запису фактичних параметрів повинні бути такими ж, як і формальних параметрів. В іншому випадку результат роботи програми буде непередбачуваним. З цього випливає, що фактичні параметри використовуються при зверненні до підпрограми з основної, а формальні параметри лише в самому модулі.
Функція називається рекурсивною, якщо її визначенні міститься виклик цієї функції. Розрізняють просту рекурсію, коли текст програми функції F безпосередньо містить виклик F, і непряму рекурсію, коли F звертається до інших функцій, які містять виклик F. Тому, за текстом програми рекурсивність не завжди визначна. Знання механізмів реалізації рекурсії допомагає ефективно використовувати її. Що відбувається, коли функція F виконує рекурсивний виклик? Насамперед, запам'ятовується поточнестан програми, необхідне продовження обчислень, коли керування знову повернеться до неї. Потім F з новими значеннями аргументів починає виконуватися заново як з новим екземпляром програми. При наступному рекурсивному виклик F все повторюється і т.д. доки черговий виклик F не призводить до будь-якого тривіального випадку, що дозволяється без рекурсивних викликів. Далі, гаразд, зворотному тому, у якому запам'ятовувалась серія викликів, проводять повернення управління. У практичних додатках важливо переконатися, що максимальна глибина рекурсивних викликів не лише кінцева, а й досить мала. В іншому випадку не уникнути переповнення стека – спеціально організованої ділянки пам'яті, де запам'ятовуються окремі стани програми-функції.
Вирішення конкретної задачі рекурсивним методом розпадається на кілька кроків, основними з яких є чотири етапи:
2. виділення бази та можливих правил її модифікації,
4. проведення відстрочених обчислень.
Перші три з них називають рекурсивною тріадою. Зупинимося на вказаних етапах докладніше.
ПараметризаціяЗавдання полягає у виявленні сукупності вихідних величин, що визначають постановку та вирішення задачі. Значення цих параметрів чи деяких із них впливають на трудомісткість розв'язання задачі. Іноді буває корисно ввести на розгляд додаткові параметри, які безпосередньо з постановкою завдання не пов'язані, але допомагають організувати рекурсію.
Виділення бази- пошук однієї або кількох підзадач, які можуть бути вирішені безпосередньо без рекурсивного виклику. Якщо база змінюватиметься у процесі обчислень, має бути вказано алгоритм її зміни. Як правило, подібна динамічна база розширюється за рахунок отримання рішень.проміжних завдань та полегшує виконання процесу відкладених обчислень. Можливе і звуження рекурсивної бази.
Декомпозиціязагального випадку є процес послідовного розкладання вихідної задачі на серію більш простих підзадач, аналогічних вихідній задачі, кожна з яких зазвичай за тією чи іншою ознакою ближча до тривіального випадку, ніж попередня. Декомпозиція передбачає наявність деяких обчислень, що передують і сприяють переходам до більш простих завдань. Їх зручно називати попередніми обчисленнями. Декомпозицію необхідно здійснювати те щоб нескладно було довести, що з будь-якому допустимому наборі значень параметрів, рано, чи пізно, вона призведе до одного з виділених тривіальних випадків, тобто до базі.
Проведення відкладених обчислень. На останньому етапі, вирішуючи одну за одною отримані на етапі декомпозиції підзавдання в порядку зворотному їхньому отриманню, ми добираємося до вирішення вихідного завдання. Цей етап безпосередньо спирається на відповідні попередні обчислення (передрахунки).
Напишіть рекурсивний алгоритм обчислення найбільшого загального дільника (НДД) двох цілих чисел.