Реферат Рекурсия

Потрібно бути дуже терплячим,

щоб навчитися терпінню.

 Є. Лец

 Не можна сказати не можна.

Д. Араго

Запровадження

Корисність, важливість та необхідність рекурсії, як однієї з концептуальних методів рішення практичних завдань підкреслювалася багатьма метрами інформатики. Посилаємося тільки двох лауреатів премії Тьюринга: американського фахівця з системному програмування Д.Кнута і англійського теоретика інформатики Ч.Хоара.

Д.Кнут широко використовував рекурсию при викладі матеріалу в який став вже класичним його тритомному випуску “Мистецтво програмування для ЕОМ” [1-3]. З іншого боку, він припускав продовжити видання книжок цієї серії й у четвертому томі жодну з двох глав назвати “Рекурсия”, повністю присвятивши її рекурсивним методам вирішення завдань [1, стор.11]. На жаль, томи із чотирьох по 7 досі не вийшли. Однак на цей час з'явилася надія, у найближчі роки (1999г.-2004г.) вони дописано й опубліковано [9].

Ч.Хоару належать такі слова “Треба віддати належне генію розробників Алгола-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

Таблиця 2.1. Поняття і терміни, пов'язані з рекурсією

Поняття,

Термін

Неформальне визначення,

пояснення

1.     Рекурсия

1. Введення у визначення об'єкта посилання сам об'єкт.

2. Прийом відомості рішення деякою завдання до вирішення серії завдань, подібних вихідної.

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

2.    

Рекурсивный

алгоритм

(процедура,

функція)

1. Алгоритм (функція, процедура) називається рекурсивним, тоді як його визначенні міститься прямий чи опосередкований виклик цього ж алгоритму.

2. Рекурсивная функція - одна з математичних уточнень інтуїтивного поняття вычислимой функції.

3.    

Пряма

рекурсія

Безпосередній виклик алгоритму (функції, процедури) F з тексту самого алгоритму F.
4.    

Косвенная

рекурсія

Циклічна послідовність викликів кількох алгоритмів (функцій, процедур) F1, F2, … Fk одне одного: F1 викликає F2, F2 викликає F3, …, Fk викликає F1 (k>1).

5.    

Рекурсивные

звернення

(рекурсивні

виклики)

Пряма чи непряма рекурсія при рекурсивних обчисленнях
6.    

Рекуррентное

співвідношення

(рекуррентная

формула)

Формула виду an+p=F(an, an+1,…, an+p-1) (p

Схожі реферати:

Навігація