РЕКУРСІЯ

МЕТОДИЧНІ ВКАЗІВКИ

до лабораторної роботи № 8

з дисципліни ”Алгоритмізація та програмування”

для студентів спеціальності 122 ”Комп’ютерні науки”

Затверджено

на засіданні кафедри інформаційних систем та мереж

Протокол №__ від _____.2018 р.

Львів-2018

Рекурсія: Методичні вказівки до лабораторної роботи № 8 / Укл.: В.А. Висоцька. – Львів: Видавництво Національного університету ”Львівська політехніка”, 2018. – 24 с.

Укладачі                     Висоцька В.А., к.т.н., доцент

Відповідальний за випуск Литвин В.В., д.т.н., професор

Рецензенти     Верес О.М., к.т.н., доцент

                          Берко А.Ю., д.т.н., професор

                          Ришковець Ю.В., к.т.н., старший викладач

Мета роботи: ознайомитись із поняттям рекурсії на мовi Сі.

1.       Теоретичні відомості

1.1.          Основні поняття

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

Приклад. Визначення функції “факторіал” задається виразом: 0!=1, n!=n(n-1)!. На основі якого утворюється множина {1,2,6,…}: 0!=1, 1!=1, 2!=2, 3!=6, …, усі її елементи якої, крім першого, визначаються рекурсивно.

Розрізняють пряму та непряму рекурсію.

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

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

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

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

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

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

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

Прикладом рекурсії в математиці є рекурентні співвідношення, які визначають певний елемент послідовності через один чи кілька попередніх. Зокрема, наприклад, функція “факторіал” задається рекурентним співвідношенням порядку 1 і початковим відрізком 0!=1. Загалом, будь-яке рекурентне співвідношення порядку k разом із заданими першими k елементами послідовності є прикладом рекурсивного означення.

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

1.2.          Приклади використання рекурсії

Приклад 8.1. Написати рекурсивну функцію для обчислення факторіала.

Повне рекурсивне визначення факторіала має такий вигляд:

Рекурентне співвідношення для обчислення факторіала позначається так:

n! = n * (n-1)!

Умова зупинки рекурсії: якщо n=0 чи n=1, то факторіал дорівнює 1.

Тоді рекурсивна функція обчислення факторіала цілого числа має такий вигляд:

int RecFact(int n) {

  if (n == 0 || n == 1) return 1;

  else return (n * RecFact(n - 1));

}

Нехай потрібно обчислити факторіал числа 3. При виклику функції RecFact(3) буде викликана функція RecFact(2), яка у свою чергу викличе RecFact(1). Для останньої функції виконається умова зупинки рекурсії (n == 1), у функцію RecFact(2) повернеться значення 1 і обчислиться значення 2 (2! = 2), яке у свою чергу повернеться до функції RecFact(3) і буде використане для обчислення значення 3!

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