Методичка_Ci / LEK8

Л е к ц и я № 8

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

Мета роботи: отримати навички роботи з рекурсивними функціями.

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

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

8.2. Приклад

Використання рекурсивної функції для обчислення факторіала.

Нехай потрібно скласти програму для обчислення факторіала будь-якого додатного числа.

#include <iostream.h>

int fact(int n);

void main()

{

int m;

cout << "\nВВедіть ціле число:";

cin >> m;

cout << "\n Факторіал числа " << m << " дорівнює " << fact (m) ;

}

int fact(int n)

{

int a;

if (n<0) return 0;

if (n==0) return 1;

a =n * fact(n-1);

return a;

}

Для від’ємного аргументу факторіала не існує, тому функція в цьому випадку повертає нульове значення. Так як факторіал 0 дорівнює 1 за означенням, то в тілі функції передбачений і цей варіант. У випадку коли аргумент функції fact() відмінний від 0 та 1, то викликаємо функцію fact() із зменшеним на одиницю значенням параметра і результат множиться на значення поточного параметра. Таким чином, у результаті вбудованих викликів функцій повертається наступний результат:

n * (n-l) * (n-2) * . . . * 2 * 1 * 1

Остання одиниця при формуванні результату належить виклику fact(0).

8.3. Порядок виконання роботи

8.3.1. Проаналізувати умову задачі.

8.3.2. Розробити алгоритм та створити програму розв’язання задачі згідно з номером варіанту.

8.3.3. Результати роботи оформити протоколом.

8.4. Варіанти завдань

Написати рекурсивні функції для розв’язання наступних задач.

1. Піднести до додатного цілого степеня дійсне ненульове число.

2. Знайти суму n членів арифметичної прогресії із заданим початковим членом та кроком.

3. Знайти суму n членів геометричної прогресії із заданим початковим членом та кроком.

Завдання підвищеної складності.

1) Дано натуральні числа ; знайти . Використати програму, що вміщує рекурсивну процедуру обчислення , що базується на співвідношенні , де — залишок від ділення на . (НСD — найбільший спільний дільник.)

2) Дано натуральні числа . Отримати , де

— залишок від ділення на 10. Використати програму, що містить в собі рекурсивну функцію обчислення .

3) Дано невід'ємні числа ; обчислити , де

(Це так звана функція Аккермана.) Використати програму, що включає рекурсивну функцію.

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

1. Вкажіть особливості опису рекурсивних функцій.

2. Охарактеризуйте математичні функції.

3. У якому файлі розміщуються прототипи математичних функцій?

73