Лабораторная работа № 6. Рекурсия
Теоретические сведения
3 принципа рекурсии
Рекурсия - это способ решения задач с помощью разбиения их на всё меньшие и меньшие подзадачи до тех пор, пока результат не сможет быть найден тривиальным способом.
- Рекурсивный алгоритм должен иметь базовый случай, когда алгоритм возвращает некое буквальное значение.
- Рекурсивный алгоритм должен изменять своё состояние и двигаться по направлению к базовому случаю.
- Рекурсивный алгоритм должен вызывать сам себя.
Пример трассировки рекурсивной функции
Проведём трассировку рекурсивной функции counter(n) для вывода на экран чисел от 1 до n. Блок-схема функции и основной программы показана на рисунке 1.
Изменение стека вызова функций показано на рисунке 2.
Вызовем функцию с аргументом равным 3.
- После вызова функции с новым аргументом 🔶, она добавляется в стек вызова функций. В элементе стека сохраняется текущее значение параметра
n. - После добавления в стек, начинается выполнение инструкций в теле функции 🟢. Как только встретится вызов функции 🔶, работа функции на вершине стека приостанавливается и в стек добавляется вызванная функция с новым значением аргумента.
- Как только будет выполнена последняя инструкция в текущей функции 🟦, она удаляется с вершины стека.
- Управление возвращается к функции, которая теперь находится на вершине стека. Начнёт выполнятся инструкция расположенная непосредственно после рекурсивного вызова 🔺.
На Python функция будет реализована следующим образом:
Задания для самостоятельной работы
Задание 1. Трассировка рекурсивной функции
Проведите трассировку рекурсивной функции to_bin(x) предназначенной для перевода числа x из десятичной системы счисления в двоичную. Добавляйте в стек все вызовы функции, отмечайте значение параметра x и результат проверки условия для продолжения рекурсии x > 0 для каждого вызова функции. Записывайте значения, выводимые функцией на экран.
Начальное значение аргумента функции зависит от вашего варианта.
Задание 2. Из десятичной в двоичную (sam02.py)
Реализуйте функциюto_bin(x) по блок-схеме на рисунке 3. Проверьте работу рекурсивной функции на числе из вашего варианта.
Задание 3. Сумма элементов списка (sam03.py)
Опишите функцию s_list(A, n) для поиска суммы элементов списка A. Реализация должна быть рекурсивной.
Рассмотрим работу функции на примере списка [5, 6, 2, 1]:
Чтобы найти сумму чисел во всём списке, нужно сложить последний элемент и сумму чисел в списке без этого элемента. Продолжая этот алгоритм мы дойдёт до случая в котором в списке останется один элемент. Тогда сумма будет равна значению этого элемента. Процесс вызова функции и обработки возвращаемых значений показан на рисунке.
Базовым случаем рекурсии будем считать ситуацию в которой список A состоит из одного элемента. В таком случае сумма будет равна
x
A[0] - первому элементу списка. Если n не равно 0, то нужно сложить элемент списка A[n] и сумму элементов до этого элемента. То есть нужно найти сумму элементов списка до индекса
x
n-1.
Используйте следующую блок-схему.
Вызовите функцию для подсчёта суммы элементов списка вашего варианта.
Задание 4. Минимальный элемент списка (sam04.py)
Опишите метод min_el(A, n) для поиска минимального элемента списка A. Реализация должна быть рекурсивной.
Для этой задачи базовый случай - список из одного элемента. Он и будет считаться минимальным. В этом случае функция должна вернуть
x
A[0]. Если в списке больше одного элемента, то будем сравнивать элемент A[n] и минимальное значение среди первых
x
n-1 элементов.
Используйте следующую блок-схему.
Вызовите функцию для поиска минимального элемента в списке из предыдущего задания.
Задание 5 (sam05.py)
Решите задачу вашего варианта.
В решении задачи обязательно должна использоваться рекурсия.
Опишите функцию nod(x, y) для вычисления наибольшего общего делителя двух целых чисел a и b.
nod(45, 60) -> 15
nod(23, 17) -> 1
nod(22, 22) -> 22
nod(1, 1) -> 1Опишите функцию sum_dig(n) для нахождения суммы цифр числа n.
sum_dig(7) -> 7
sum_dig(387) -> 18
sum_dig(0) -> 0
sum_dig(100) -> 1Опишите функцию trib(n) для нахождения n-го числа последовательности трибоначчи: \[
t_0=0, t_1=0, t_2=1, t_n=t_{n-1}+t_{n-2}+t_{n-3}
\]
trib(2) -> 1
trib(4) -> 2
trib(0) -> 0
trib(10) -> 81Опишите функцию invert(s) для инвертирования строки s.
s = 'наоборот'
invert(s, len(s) - 1) -> 'торобоан'
s = 'шалаш'
invert(s, len(s) - 1) -> 'шалаш'
s = 'а'
invert(s, len(s) - 1) -> 'а'Опишите функцию is_prime(x , d) с помощью которой можно определить, является ли x простым числом.
is_prime(30, 29) -> False
is_prime(41, 40) -> TrueОпишите функцию prod(n) с помощью которой можно вычислить произведение целых чисел от 1 до n.
prod(7) -> 720
prod(1) -> 1
prod(0) -> 0
prod(12) -> 479001600Опишите функцию cannon(h) с помощью которой можно рассчитать количество шаров в пирамиде, состоящей из h уровней:
cannon(1) -> 1
cannon(4) -> 30
cannon(13) -> 819
cannon(100) -> 338350Опишите функцию nod(x, y) для вычисления наибольшего общего делителя двух целых чисел a и b.
nod(45, 60) -> 15
nod(23, 17) -> 1
nod(22, 22) -> 22
nod(1, 1) -> 1Опишите функцию sum_dig(n) для нахождения суммы цифр числа n.
sum_dig(7) -> 7
sum_dig(387) -> 18
sum_dig(0) -> 0
sum_dig(100) -> 1Опишите функцию trib(n) для нахождения n-го числа последовательности трибоначчи: \[
t_0=0, t_1=0, t_2=1, t_n=t_{n-1}+t_{n-2}+t_{n-3}
\]
trib(2) -> 1
trib(4) -> 2
trib(0) -> 0
trib(10) -> 81Опишите функцию invert(s) для инвертирования строки s.
s = 'наоборот'
invert(s, len(s) - 1) -> 'торобоан'
s = 'шалаш'
invert(s, len(s) - 1) -> 'шалаш'
s = 'а'
invert(s, len(s) - 1) -> 'а'Опишите функцию is_prime(x , d) с помощью которой можно определить, является ли x простым числом.
is_prime(30, 29) -> False
is_prime(41, 40) -> TrueОпишите функцию prod(n) с помощью которой можно вычислить произведение целых чисел от 1 до n.
prod(7) -> 720
prod(1) -> 1
prod(0) -> 0
prod(12) -> 479001600Опишите функцию cannon(h) с помощью которой можно рассчитать количество шаров в пирамиде, состоящей из h уровней:
cannon(1) -> 1
cannon(4) -> 30
cannon(13) -> 819
cannon(100) -> 338350Задание 6 (sam06.py)
Решите задачу вашего варианта.
В решении задачи обязательно должна использоваться рекурсия. Нельзя использовать циклы.
Напишите рекурсивную функцию palindrom(s) для определения, является ли строка s палиндромом.
palindrom('шалаш') -> True
palindrom('палатка') -> False
palindrom('1001') -> True
palindrom('451') -> FalseНапишите рекурсивную функцию sum_even(n) для нахождения суммы всех положительных чётных чисел меньших или равных n.
sum_even(6) -> 12
sum_even(2) -> 2
sum_even(0) -> 0
sum_even(50) -> 650Напишите рекурсивную функцию is_power(n) с помощью которой можно определить, является ли число n степенью двойки.
is_power(1) -> True
is_power(8) -> True
is_power(7) -> False
is_power(10) -> FalseНапишите рекурсивную функцию count7(n) с помощью которой можно посчитать, сколько раз цифра 7 встречается в числе n.
count7(523) -> 0
count7(0) -> 0
count7(7777) -> 4
count7(125797) -> 2Напишите рекурсивную функцию powerN(b, n) для возведения числа b в степень n.
powerN(2, 3) -> 8
powerN(3, 1) -> 3
powerN(6, 0) -> 1
powerN(2, 8) -> 256Функция Аккермана определена следующим образом: \[
A(m, n) =
\begin{cases}
n + 1 & m = 0\\
A(m - 1, 1)& m > 0, n = 0\\
A(m - 1, A(m, n - 1))& m > 0, n > 0\\
\end{cases}
\] Напишите рекурсивную функцию A(m, n) для вычисления значения функции для двух чисел m и n.
A(2, 2) -> 7
A(3, 2) -> 29
A(2, 1) -> 5Напишите рекурсивную функцию coin_flip(s) которая принимает на вход строку s. Строка может состоять только из комбинации двух символов - “О” или “Р”. Функция должна посчитать, сколько раз в строке s встречается буква “Р”.
coin_flip("ОРРО") -> 2
coin_flip("ООOOOO") -> 0
coin_flip("РРРРР") -> 5
coin_flip("") -> 0Напишите рекурсивную функцию palindrom(s) для определения, является ли строка s палиндромом.
palindrom('шалаш') -> True
palindrom('палатка') -> False
palindrom('1001') -> True
palindrom('451') -> FalseНапишите рекурсивную функцию sum_even(n) для нахождения суммы всех положительных чётных чисел меньших или равных n.
sum_even(6) -> 12
sum_even(2) -> 2
sum_even(0) -> 0
sum_even(50) -> 650Напишите рекурсивную функцию is_power(n) с помощью которой можно определить, является ли число n степенью двойки.
is_power(1) -> True
is_power(8) -> True
is_power(7) -> False
is_power(10) -> FalseНапишите рекурсивную функцию count7(n) с помощью которой можно посчитать, сколько раз цифра 7 встречается в числе n.
count7(523) -> 0
count7(0) -> 0
count7(7777) -> 4
count7(125797) -> 2Напишите рекурсивную функцию powerN(b, n) для возведения числа b в степень n.
powerN(2, 3) -> 8
powerN(3, 1) -> 3
powerN(6, 0) -> 1
powerN(2, 8) -> 256Функция Аккермана определена следующим образом: \[
A(m, n) =
\begin{cases}
n + 1 & m = 0\\
A(m - 1, 1)& m > 0, n = 0\\
A(m - 1, A(m, n - 1))& m > 0, n > 0\\
\end{cases}
\] Напишите рекурсивную функцию A(m, n) для вычисления значения функции для двух чисел m и n.
A(2, 2) -> 7
A(3, 2) -> 29
A(2, 1) -> 5Напишите рекурсивную функцию coin_flip(s) которая принимает на вход строку s. Строка может состоять только из комбинации двух символов - “О” или “Р”. Функция должна посчитать, сколько раз в строке s встречается буква “Р”.
coin_flip("ОРРО") -> 2
coin_flip("ООOOOO") -> 0
coin_flip("РРРРР") -> 5
coin_flip("") -> 0