Решение задач на тему «Рекурсия»

1. О пи сать рекурсивные функции Fact(N) и Fact2(N) вещественного типа, вычисляющие значе-
ния факториала N! и двойного факториала N!! соответственно (N > 0 — параметр целого ти-
па).
2. Описать рекурсивную функцию PowerN(x, n) вещественного типа, находящую значение n-й
степени числа x по формуле: x0 = 1, xn = x·xn–1 при n > 0, xn = 1 / x –n при n < 0 (x >= 0 – вещест-
венное число, n – целое).
3. Описать рекурсивную функцию SqrtK(x, k, n) вещественного типа, находящую приближенное
значение корня k-й степени из числа x по формуле:
y(0) = 1, y(n + 1) = y(n) – (y(n) – x / yk–1(n)) / k,
где y(n) обозначает SqrtK(x, k, n) (x – вещественный параметр, k и n – целые; x > 0, k > 1, n > 0).
4. Описать рекурсивную функцию FibRec(N) целого типа, вычисляющую N-е число Фибоначчи
F(N) по формуле: F(1) = F(2) = 1, F(k) = F(k–2) + F(k–1), k = 3, 4, … С помощью этой функции
найти пять чисел Фибоначчи с указанными номерами и вывести эти числа вместе с количест-
вом рекурсивных вызовов функции FibRec, потребовавшихся для их нахождения.
5. Описать рекурсивную функцию C(m, n) целого типа, находящую число сочетаний из n эле-
ментов по m, используя формулу: C(0, n) = C(n, n) = 1, C(m, n) = C(m, n–1) + C(m–1, n–1) при
0 < m < n (m и n — целые параметры; n > 0, 0 <= m <= n). Дано число N и пять различных зна-
чений M. Вывести числа C(M, N) вместе с количеством рекурсивных вызовов функции C, по-
требовавшихся для их нахождения.
6. Описать рекурсивную функцию NOD(A, B) целого типа, находящую наибольший общий де-
литель двух натуральных чисел A и B, используя алгоритм Евклида:
NOD(A, B) = NOD(B mod A, A), если A <> 0; NOD(0, B) = B.
С помощью этой функции найти наибольшие общие делители пар A и B, A и C, A и D, если
даны числа A, B, C, D.
7. Описать рекурсивную функцию MinRec(A, N) вещественного типа, которая находит мини-
мальный элемент вещественного массива A размера N, не используя оператор цикла. С по-
мощью функции MinRec найти минимальные элементы массивов A, B, C размера NA, NB, NC
соответственно.
8. Описать рекурсивную функцию Digits(S) целого типа, находящую количество цифр в строке
S без использования оператора цикла. С помощью этой функции найти количество цифр
в заданной строке.
9. Описать рекурсивную функцию Simm(S) логического типа, проверяющую, является ли сим-
метричной строка S, без использования оператора цикла. С помощью этой функции прове-
рить заданную строку.
10. Задано положительное и отрицательное число в двоичной системе. Составить программу вы-
числения суммы этих чисел, используя функцию сложения чисел в двоичной системе счис-
ления.
11. Описать рекурсивную функцию Root (а, b, ε), которая методом деления отрезка пополам на-
ходит с точностью ε корень уравнения f(x) = 0 на отрезке [а, b] (считать, что ε > 0, а < b,
f(a) – f(b) < 0 и f(x) — непрерывная и монотонная на отрезке [а, b] функция).
12. Описать функцию min(X) для определения минимального элемента линейного массива X,
введя вспомогательную рекурсивную функцию minl(k), находящую минимум среди послед-
них элементов массива X, начиная с k-го.
13. Описать рекурсивную логическую функцию Simm(S, I, J), проверяющую, является ли сим-
метричной часть строки S, начинающаяся i-м и заканчивающаяся j-м ее элементами.
14. Составить программу для нахождения числа, которое образуется из данного натурального
числа при записи его цифр в обратном порядке. Например, для числа 1234 получаем резуль-
тат 4321.
15. Составить программу для перевода данного натурального числа в р-ичную систему счисле-
ния (2 ≤ р ≤ 9).