1. Дано цілі числа ( ). Знайти їх найбільший спільний дільник (НСД). Для розв’язання задачі визначити й використати рекурсивну функцію обчислення НСД, засновану на співвідношенні: НСД (n, 0) = n; НСД ( ) = = НСД ( ), де – остача від ділення на (m ≠ 0).
2. Числа Фібоначчі , , , … визначаються за таким правилом: , , ( ). Розробити рекурсивну функцію обчислення un для даного невід’ємного цілого n, що базується на безпосередньому використанні співвідношення .
3. Дано невід’ємні цілі числа n та m. Написати рекурсивну функцію для обчислення функції Аккермана:
4. Скласти рекурсивну функцію, що обчислює суму двох цілих невід’ємних чисел шляхом багаторазового додавання числа 1. Наприклад, 6 + 10 = (6 + + 1) + (10 – 1) = (7 + 1) + (9 – 1) = ...
5. Описати функцію для обчислення з використанням рекурсії:
Дано цілі числа n і m ( , ). За допомогою описаної функції знайти значення .
6. Дано натуральні числа m, , , …, ( ). Обчислити найбільший спільний дільник чисел , , …, : . Відомо, що для будь-якого натурального виконується таке співвідношення:
.
Визначити рекурсивну функцію обчислення найбільшого спільного дільника елементів масиву натуральних чисел.
7. Дано натуральне число n і дійсне число ( ). Обчислити значення ланцюгового дробу, розробивши для цього рекурсивну функцію:
.
8. Описати функцію відшукання мінімального елемента масиву з n дійсних чисел, де n – натуральне число. У функції не повинно бути явної організації циклу. Скористатися цією функцією для пошуку мінімуму в заданому одновимірному масиві.
9. Описати рекурсивну функцію сортування за зростанням масиву з n цілих чисел. Ідея методу така: помістити найменший елемент на першу позицію, після чого відсортувати частину масиву, що залишилася, за допомогою рекурсивного виклику.
10. Описати рекурсивну функцію з одним аргументом, яка без використання операторів циклу перевіряє, чи є одновимірний цілочисловий масив симетричним.
11. Дано квадратну матрицю A розміру , де n – натуральне число. Обчислити її визначник. Використати рекурсивну функцію обчислення визначника розкладанням за першим рядком.
12. Описати рекурсивну функцію з трьома аргументами (одновимірний дійсний масив і два індекси-обмежники), що не використовує оператори циклу. Функція повинна розвертати на 180º частину одновимірного дійсного масиву від першого індексу-обмежника до другого включно. Протестувати цю функцію для таких випадків:
а) перший індекс-обмежник менший за другий;
а) перший індекс-обмежник більший від другого;
б) індекси-обмежники рівні.
Контрольні запитання
1. Що таке рекурсія?
2. Що повинно бути у функції для правильної організації рекурсії?
3. Що таке неявна рекурсія?
4. Як треба описувати функції для неявної рекурсії?
5. Чи може бути нескінченним рекурсивний процес?
6. Що можна сказати про обсяги пам’яті, які необхідні для роботи рекурсивних функцій?
7. Перелічіть переваги та недоліки звичайних і рекурсивних функцій.
8. Маємо таку функцію:
int f(int n) { if (n = 0) return 0; return n + f(n - 1); }
Що вона повинна обчислювати? Чи є синтаксичні помилки в її коді? Виходячи із з’ясованого Вами призначення функції, зробіть висновки про наявність логічних помилок в її коді. Зробіть пояснення і виправлення помилок у разі їх наявності.
9. Маємо таку функцію:
int f(double *a, int n) { if (n == 1) *a; return *a * f(a, n - 1); }
Що вона повинна обчислювати? Чи є синтаксичні помилки в її коді? Виходячи із з’ясованого Вами призначення функції, зробіть висновки про наявність логічних помилок в її коді. Зробіть пояснення і виправлення помилок у разі їх наявності.
10. Маємо таку функцію:
int f(double *a, int n) { return n > 1 ? *a * f(a, n - 1) : *a; }
Що вона повинна обчислювати? Чи є синтаксичні помилки в її коді? Виходячи із з’ясованого Вами призначення функції, зробіть висновки про наявність логічних помилок в її коді. Зробіть пояснення і виправлення помилок у разі їх наявності.
11. Маємо таку функцію:
int f(double *p, double *q, double *a, int n) { return n == 1 ? *p = *a, *q = *a, 0 : f(p, q, a, n - 1), *p < *(a + n - 1) ? *p = *(a + n - 1) : 0, *q > *(a + n - 1) ? *q = *(a + n - 1) : 0, 0; }
Що вона повинна обчислювати? Чи є синтаксичні помилки в її коді? Виходячи із з’ясованого Вами призначення функції, зробіть висновки про наявність логічних помилок в її коді. Зробіть пояснення і виправлення помилок у разі їх наявності.
Список літератури
1. Страуструп, Б. Язык программирования Си++ : Второе издание / Б. Страуструп. – К. : ДиаСофт, 1993. – Ч. 1. – 264 с. ; Ч. 2. – 296 с.
2. Керниган, Б. Язык программирования Си / Б. Керниган, Д. Ритчи. – М. : Финансы и статистика, 1992. – 272 с.
3. Либерти, Джесс. Освой самостоятельно С++ за 21 день : учеб. пособ. / Джесс Либерти. – М. : Вильямс, 2001. – 816 с.
4. Подбельский, В. В. Программирование на языке Си / В. В. Подбельский, С. С. Фомин. – М. : Финансы и статистика, 1999. – 600 с.
5. Подбельский, В. В. Язык Си++ / В. В. Подбельский. – М. : Финансы и статистика, 1999. – 560 с.
6. Савитч, Уолтер. Язык C++. Курс объектно-ориентированного программирования / Уолтер Савитч. – М. : Вильямс, 2001. – 704 с.
Навчальне видання
Методичні вказівки
до лабораторної роботи «Рекурсивні функції в програмах мовою C++»
з курсу «Програмування» для студентів напряму 6.040302 – Інформатика і курсу «Програмування та алгоритмічні мови» для студентів напряму 6.040303 – Системний аналіз
Укладачі: БЕЗМЕНОВ Микола Іванович,
БЕЗМЕНОВА Ольга Миколаївна
Відповідальний за випуск О. С. Куценко
Роботу до видання рекомендував О. В. Горелий
За авторською редакцією
План 2013 р., поз. 4/76–13
Підписано до друку __.__.2013 р. Формат 60´84 1/16. Папір офсетний.
( 
). Знайти їх найбільший спільний дільник (НСД). Для розв’язання задачі визначити й використати рекурсивну функцію обчислення НСД, засновану на співвідношенні: НСД (n, 0) = n; НСД ( 
), де 
– остача від ділення 
на 
(m ≠ 0).
, 
, 
, … визначаються за таким правилом: 
, 
, 
( 
). Розробити рекурсивну функцію обчислення un для даного невід’ємного цілого n, що базується на безпосередньому використанні співвідношення 
з використанням рекурсії:
, 
). За допомогою описаної функції знайти значення 
, 
, …, 
( 
). Обчислити найбільший спільний дільник чисел 
. Відомо, що для будь-якого натурального 
виконується таке співвідношення:
.
( 
). Обчислити значення ланцюгового дробу, розробивши для цього рекурсивну функцію:
.
, де n – натуральне число. Обчислити її визначник. Використати рекурсивну функцію обчислення визначника розкладанням за першим рядком.