Рекурсивні функції

Теоретичні основи

Кожна з функцій може викликати інші функції, у тому числі звертатися до самої себе. Функція, що звертається до самої себе, називається рекурсивною. Рекурсія може бути і неявною, коли функція first викликає функцію second, а та в свою чергу викликає функцію first. У зв’язку з наявністю взаємних посилань функцій однієї на іншу виникає проблема, що зумовлена вимогою C++ до описів: спочатку описати, потім використовувати. При неявній рекурсії обов’язковим є випереджальний опис функції за допомогою прото­типу.

Обов’язковим елементом в описі будь-якого рекурсивного процесу є дея­ке твердження (оператор), що визначає умову завершення рекурсії; іноді вона називається опорною умовою. У цій умові може бути задане яке-небудь фіксо­ване значення, що обов’язково буде досягнуте в ході рекурсивного обчислення, до­зволяючи тим самим організувати своєчасне зупинення процесу. Крім того, по­винен бути другий елемент – спосіб вираження одного кроку розв’язання за до­помогою іншого, простішого. Кількість рівнів вкладеності не обмежена і може бути досить великою.

Кожен виклик рекурсивної функції повинен наближати випадок, що зу­пиняє рекурсивні виклики, інакше виконання функції ніколи не припиниться через нескінченний ланцюжок рекурсивних викликів. У дійсності, не­скінчен­ний ланцюжок рекурсивних викликів не може реалізуватися, оскільки відбува­ється аварійне завершення програми. Найпростішим способом гарантування вико­нання опорної умови є зменшення деякої додатної величини до до­сягнення деякого «малого» значення.

Особливістю реалізації рекурсивних функцій є те, що в програмі існує тільки один екземпляр коду цієї функції. На кожному рівні рекурсії здійс­нюється нове звернення до цього коду. Рис. 1.1 ілюструє виконання рекурсив­ного процесу з трьома рівнями рекурсивного виклику; правда, для простоти по­яснення вважається, що на кожному рівні створюється новий екземпляр коду функції. Розглянемо послідовність дій що виконується в цьому випадку.

Рис. 1.1 – Схема виконання рекурсивного процесу
(УЗР – умова завершення рекурсії)

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

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

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