Розділ 9. Рекурсія

9.1. Поняття рекурсії

Рекурсія – це спосіб організації обчислювального процесу, при якому функція звертається сама до себе. Такі звернення називаються рекурсивними викликами, а функція, що містить рекурсивні виклики, – рекурсивною [4]. Це означає, що для вирі­шення певної задачі потрібно серед допоміжних підзадач вирішити таку саму задачу, тільки з іншими значеннями параметрів.

Розрізняють пряму та непряму рекурсію. Пряма рекурсія полягає в тому, що певна функція у своєму тілі викликає сама себе, а непряма – коли дві чи більше функцій викликають одна одну.

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

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

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

• в стеку резервується місце для формальних параметрів, куди запису­ються значення фактичних параметрів. Переважно це виконується в порядку, зво­ротному до їхнього місця у списку параметрів функції;
• при виклику функції в стек записується точка повернення, тобто адреса тої частини програми, де міститься виклик функції;
• на початку тіла функції у стеку резервується місце для локальних (автоматичних) змінних.

Зазначені змінні створюють групу (фрейм стека). Стек “пам’ятає історію” рекурсивних викликів у вигляді послідовності (ланцюжка) таких фреймів. Про­грама у кожний конкретний момент працює з останнім викликом і з останнім фреймом. По завершенні рекурсії програма повертається до попередньої версії рекурсивної функції й до попереднього фрейму у стеку.

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

1.2. Рекурентні співвідношення

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

(Для ознайомлення з повним текстом статті необхідно залогінитись)