4.4 Контрольні запитання

1. Що таке ітераційний цикл?

2. Які причини зациклювання програм?

3. За яких умов цикл не виконується?

4. У чому полягають особливості застосування операторів break та continue?

5. Яке призначення функцій С++? Яка роль функції main()?

6. Що таке прототип функції? Що таке визначення функції?

7. Дати поняття рекурсивних функцій. Технологія припинення рекурсивного виклику.

8. Чим пряма рекурсія відрізняється від непрямої?

9. Якими бувають оператори виклику функцій?

10. Як викликається функція, що повертає значення void?

11. Як викликається функція, що повертає значення будь-якого типу, який відрізняється від типу void?

12. Значення якого типу повертає функція, якщо тип не вказано?

13. Скільки значень може повернути функція?

Рекурсивні функції Лабораторна робота 5

Мета роботи.

• вивчити особливості рекурсивних процесів

• опанувати технологію рекурсивних обчислень

• навчитися розробляти алгоритми та програми із застосуванням рекурсивних функцій

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

Означення називається рекурсивним, якщо воно задає елементи множини за допомогою інших елементів цієї самої множини. Об' єкти, що задані рекурсивним означенням, також називаються рекурсивними. Під терміном "рекурсивно задана функція" розуміється така функція, значення якої для данноrо apгумента обчислюється за допомогою значень для попередніх apгументов. При кожній конкретній реалізації процес обчислення такої функції задається рекурентною послідовністю. У практиці обчислень це пов'язано з тим, що, маючи справу з реальною функцією, ми не обчислюємо її в реальному завданні на усій числовій осі, а обчислюємо для деякої кінцевої послідовності значень apгументов.

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

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

• умову продовження рекурсії (крок рекурсії);

• умову закінчення рекурсії.

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

1. Функція задається безпосередньо у вигляді числових значень для деякої конечної множини початкових значень аргументу .

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

В результаті отримуємо peкуррентні співвідношення, що описують рекурсивно задану функцію , рівносильну послідовності .

Отриманий запис цих двох етапів

називається рекурентним співвідношенням.

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

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

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

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

int Fib(int n) { if (n == 0) return 0; else if (n == 1) return 1; else return Fib(n–1)+Fib(n–2); }