Лабораторная работа № 6. Рекурсия

ПредупреждениеНеобходимые файлы

Перед началом работы, cкачайте файл с заданиями, выполняемыми без компьютера.

Теоретические сведения

3 принципа рекурсии

Рекурсия - это способ решения задач с помощью разбиения их на всё меньшие и меньшие подзадачи до тех пор, пока результат не сможет быть найден тривиальным способом.

  • Рекурсивный алгоритм должен иметь базовый случай, когда алгоритм возвращает некое буквальное значение.
  • Рекурсивный алгоритм должен изменять своё состояние и двигаться по направлению к базовому случаю.
  • Рекурсивный алгоритм должен вызывать сам себя.

Пример трассировки рекурсивной функции

Проведём трассировку рекурсивной функции counter(n) для вывода на экран чисел от 1 до n. Блок-схема функции и основной программы показана на рисунке 1.

Рисунок 1

Изменение стека вызова функций показано на рисунке 2.

Рисунок 2

Вызовем функцию с аргументом равным 3.

  1. После вызова функции с новым аргументом 🔶, она добавляется в стек вызова функций. В элементе стека сохраняется текущее значение параметра n.
  2. После добавления в стек, начинается выполнение инструкций в теле функции 🟢. Как только встретится вызов функции 🔶, работа функции на вершине стека приостанавливается и в стек добавляется вызванная функция с новым значением аргумента.
  3. Как только будет выполнена последняя инструкция в текущей функции 🟦, она удаляется с вершины стека.
  4. Управление возвращается к функции, которая теперь находится на вершине стека. Начнёт выполнятся инструкция расположенная непосредственно после рекурсивного вызова 🔺.

На Python функция будет реализована следующим образом:

Рисунок 3

Задания для самостоятельной работы

Задание 1. Трассировка рекурсивной функции

Проведите трассировку рекурсивной функции to_bin(x) предназначенной для перевода числа x из десятичной системы счисления в двоичную. Добавляйте в стек все вызовы функции, отмечайте значение параметра x и результат проверки условия для продолжения рекурсии x > 0 для каждого вызова функции. Записывайте значения, выводимые функцией на экран.

Рисунок 4

Начальное значение аргумента функции зависит от вашего варианта.

to_bin(15)
to_bin(14)
to_bin(10)
to_bin(11)
to_bin(12)
to_bin(13)
to_bin(9)
to_bin(15)
to_bin(14)
to_bin(10)
to_bin(11)
to_bin(12)
to_bin(13)
to_bin(9)

Задание 2. Из десятичной в двоичную (sam02.py)

Реализуйте функциюto_bin(x) по блок-схеме на рисунке 4. Проверьте работу рекурсивной функции на числе из вашего варианта.

Задание 3. Сумма элементов списка (sam03.py)

Опишите функцию s_list(A) для поиска суммы элементов списка A. Реализация должна быть рекурсивной.

Рассмотрим работу функции на примере списка [5, 6, 2, 1]:

Пример вызова функции s_list

Пример вызова функции s_list

Чтобы найти сумму чисел во всём списке, нужно сложить последний элемент и сумму чисел в списке без этого элемента. Продолжая этот алгоритм мы дойдёт до случая в котором в списке нет элементов. Тогда сумма будет равна нулю. Процесс вызова функции и обработки возвращаемых значений показан на рисунке.

Длину списка сохраним в переменной n. Базовым случаем рекурсии будем считать ситуацию в которой список A пуст. В таком случае сумма будет равна x 0. Если n не равно 0, то нужно сложить элемент списка A[n-1] и сумму элементов до этого элемента. Чтобы получить срез списка без последнего элемента запишем выражение x A[:n-1].

Используйте следующую блок-схему.

Рисунок 5

Вызовите функцию для подсчёта суммы элементов списка вашего варианта.

lst = [4, 5, 9]
lst = [9, 5, -1, 9]
lst = [15, 3, 6]
lst = [3, 12, 11, 8]
lst = [1, 9, -4, 2, 6]
lst = [1, 9]
lst = [1, 9, -4, 2, 6]
lst = [4, 5, 9]
lst = [9, 5, -1, 9]
lst = [15, 3, 6]
lst = [3, 12, 11, 8]
lst = [1, 9, -4, 2, 6]
lst = [1, 9]
lst = [1, 9, -4, 2, 6]

Задание 4. Минимальный элемент списка (sam04.py)

Опишите функцию min_el(A) для поиска минимального элемента списка A. Реализация должна быть рекурсивной.

Длину списка сохраним в переменной n. Для этой задачи базовый случай - список из одного элемента (n = 1). Данный элемент и будет считаться минимальным. В этом случае функция должна вернуть x A[0]. Если в списке больше одного элемента, то будем сравнивать элемент A[n - 1] и минимальное значение среди первых x n-1 элементов.

Используйте следующую блок-схему. Самостоятельно запишите условия в инструкциях ветвления вместо подчёркиваний.

Рисунок 6

Вызовите функцию для поиска минимального элемента в списке из предыдущего задания.

Задание 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) с помощью которой можно определить, является ли x простым числом.

is_prime(30)    -> False
is_prime(41)    -> True

Опишите функцию prod(n) с помощью которой можно вычислить произведение целых чисел от 1 до n.

prod(7)     -> 720
prod(1)     -> 1
prod(0)     -> 0
prod(12)    -> 479001600

Опишите функцию cannon(h) с помощью которой можно рассчитать количество шаров в пирамиде, состоящей из h уровней:

Пирамида из 4 уровней

Пирамида из 4 уровней
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) с помощью которой можно определить, является ли x простым числом.

is_prime(30)    -> False
is_prime(41)    -> True

Опишите функцию prod(n) с помощью которой можно вычислить произведение целых чисел от 1 до n.

prod(7)     -> 720
prod(1)     -> 1
prod(0)     -> 0
prod(12)    -> 479001600

Опишите функцию cannon(h) с помощью которой можно рассчитать количество шаров в пирамиде, состоящей из h уровней:

Пирамида из 4 уровней

Пирамида из 4 уровней
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