Краткие теоретические и учебно-методические материалы по теме лабораторной работы
Рекурсивным называтся любой объект, который частично определяется через себя.
Например, приведенное ниже определение двоичного кода является рекурсивным:
<двоичный код> ::= <двоичная цифра> | <двоичный код><двоичная цифра>
<двоичная цифра> ::= 0 | 1
Здесь для описания понятия были использованы, так называемые, металингвистический формулы Бэкуса-Наура (язык БНФ); знак "::=" обозначает "по определению есть", знак "|" — "или".
Вообще, в рекурсивном определении должно присутствовать ограничение, граничное условие, при выходе на которое дальнейшая инициация рекурсивных обращений прекращается.
Классический пример, без которого не обходятся ни в одном рассказе о рекурсии, — определение факториала. С одной стороны, факториал определяется так: n!=1*2*3*...*n. С другой стороны,
Граничным условием в данном случае является n<=1.
Пример 2. Определим функцию K(n), которая возвращает количество цифр в заданном натуральном числе n:
Обращение к рекурсивной подпрограмме ничем не отличается от вызова любой другой подпрограммы. При этом при каждом новом рекурсивном обращении в памяти создаётся новая копия подпрограммы со всеми локальными переменными. Такие копии будут порождаться до выхода на граничное условие. Очевидно, в случае отсутствия граничного условия, неограниченный рост числа таких копий приведёт к аварийному завершению программы за счёт переполнения стека.
Порождение все новых копий рекурсивной подпрограммы до выхода на граничное условие называется рекурсивным спуском. Максимальное количество копий рекурсивной подпрограммы, которое одновременно может находиться в памяти компьютера, называется глубиной рекурсии. Завершение работы рекурсивных подпрограмм, вплоть до самой первой, инициировавшей рекурсивные вызовы, называется рекурсивным подъёмом.
Пример: Нахождение факториала
double Factorial(int N)
{
double F;
if (N<=1) F=1.; else F=Factorial(N-1)*N;
return F;
}
Пример 2.
int K(int N)
{
int Kol;
if (N<10) Kol=1; else Kol=K(N/10)+1;
return Kol;
}
Пример 3.
int C(int m, int n)
{
int f;
if (m==0||m==n) f=1; else f=C(m, n-1)+C(m-1, n-1);
return f;
}
Задания для лабораторной работы:
1: От 1 до n
Дано натуральное число n. Выведите все числа от 1 до n.
Ввод |
Вывод |
5 |
1 2 3 4 5 |
2: От A до B
Даны два целых числа A и В (каждое в отдельной строке). Выведите все числа от A до B включительно, в порядке возрастания, если A < B, или в порядке убывания в противном случае.
Ввод |
Вывод |
5 1 |
5 4 3 2 1 |
3: Функция Аккермана
В теории вычислимости важную роль играет функция Аккермана A(m,n), определенная следующим образом:
A(m,n)=⎧⎩⎨n+1A(m−1,1)A(m−1,A(m,n−1))m=0m>0,n=0m>0,n>0
Даны два целых неотрицательных числа m и n, каждое в отдельной строке. Выведите A(m,n).
Ввод |
Вывод |
2 2 |
7 |
4: Точная степень двойки
Дано натуральное число N. Выведите слово YES, если число N является точной степенью двойки, или слово NO в противном случае.
Операцией возведения в степень пользоваться нельзя!
Ввод |
Вывод |
8 |
YES |
3 |
NO |
5: Сумма цифр числа
Дано натуральное число N. Вычислите сумму его цифр.
При решении этой задачи нельзя использовать строки, списки, массивы (ну и циклы, разумеется).
Ввод |
Вывод |
179 |
17 |
6: Цифры числа справа налево
Дано натуральное число N. Выведите все его цифры по одной, в обратном порядке, разделяя их пробелами или новыми строками.
При решении этой задачи нельзя использовать строки, списки, массивы (ну и циклы, разумеется). Разрешена только рекурсия и целочисленная арифметика.
Ввод |
Вывод |
179 |
9 7 1 |
7: Цифры числа слева направо
Дано натуральное число N. Выведите все его цифры по одной, в обычном порядке, разделяя их пробелами или новыми строками.
При решении этой задачи нельзя использовать строки, списки, массивы (ну и циклы, разумеется). Разрешена только рекурсия и целочисленная арифметика.
Ввод |
Вывод |
179 |
1 7 9 |
8: Проверка числа на простоту
Дано натуральное число n>1. Проверьте, является ли оно простым. Программа должна вывести слово YES, если число простое и NO, если число составное. Алгоритм должен иметь сложность O(logn).
Ввод |
Вывод |
2 |
YES |
4 |
NO |
Указание. Понятно, что задача сама по себе нерекурсивна, т.к. проверка числа n на простоту никак не сводится к проверке на простоту меньших чисел. Поэтому нужно сделать еще один параметр рекурсии: делитель числа, и именно по этому параметру и делать рекурсию.