Министерство науки и высшего образования Российской Федерации

Федеральное государственное бюджетное образовательное учреждение

высшего образования

«ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ

УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ» (ТУСУР)

Кафедра безопасности информационных систем (БИС)

Рекурсия. Типы рекурсий

Отчет по лабораторной работе №4

по дисциплине «Языки программирования»

Студент гр.739-1

_______ М. Д. Климанов

12.11.2020

Принял

Младший научный сотрудник

______ В. А. Полюга

12.11.2020

Томск 2020

Содержание

Содержание 2

1 Введение 3

2 Ход работы 4

2.1 Линейная рекурсия 5

2.2 Повторная рекурсия 5

2.3 Взаимная рекурсия 6

2.4 Каскадная рекурсия 6

2.5 Удаленная рекурсия 7

3 Заключение 8

Приложение А 9

1 Введение

Цель работы: изучение различных типов рекурсий и способов их применения для решения практических задач.

2 Ход работы

Функция называется рекурсивной, если во время ее обработки возникает ее повторный вызов, либо непосредственно, либо косвенно, путем цепочки вызовов других функций.

Рекурсивное определение функции должно предусматривать критерий останова, иначе дерево рекурсивных вызовов может оказаться бесконечным. Рассмотрим основные типы рекурсий.

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

Частный случай линейной рекурсии с отсутствующими предварительными или отложенными вычислениями называется повторительной рекурсией.

Рекурсию называют каскадной, если она не является линейной. Рекурсивные вызовы могут возникнуть более одного раза, образуя древовидную схему вызовов.

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

Циклическая последовательность вызовов нескольких функций F1, F2, …, Fk (процедур, алгоритмов) друг друга: F1 вызывает F2, F2 вызывает F3, …, Fk вызывает F1 (k>1), называют косвенной или взаимной рекурсией.

2.1 Линейная рекурсия

Для первой программы (линейной рекурсии) выбрана тема факториала. Т.е. входными данными будет натуральное число, а выходными соответственно факториал этого числа.

Пример программы представлен на рисунке 2.1.1.

Пример программы рисунок 2.1.1.

Результат работы программы представлен на рисунке 2.1.2.

Рисунок 2.1.2 – Результат работы первой программы

Листинг кода можно найти в приложении А.

2.2 Повторная рекурсия

Повторная рекурсия является частным случаем линейной рекурсии, единственное, в чем есть отличия это вычисления перед рекурсивным вызовом.

Программа, которая приведена на рисунке 2.2.1, высчитывает наибольший общий делитель.

Пример программы рисунок 2.2.1.

Результат работы программы представлен на рисунке 2.2.2.

Рисунок 2.2.2 – Повторная рекурсия

Как видно из рисунка программа выдает верный результат – значит исходный код программы написан без ошибок.

2.3 Взаимная рекурсия

Взаимная рекурсия характеризуется взаимным вызовом двух и более функций.

Пример программы представлен на рисунке 2.3.1.

Пример программы рисунок 2.3.1.

Результат работы программы приведен на рисунке 2.3.2.

Рисунок 2.3.2 – Взаимная рекурсия

2.4 Каскадная рекурсия

Этот вид рекурсии похож на линейную, главное отличие в том, что рекурсивный вызов функции может происходить одновременно два и более раза за один рекурсивный срез. Наиболее известная каскадная функция - это функция для вычисления чисел Фибоначчи.

Пример программы представлен на рисунке 2.4.1.

Пример программы рисунок 2.4.1.

Результат работы программы приведен на рисунке 2.4.2

Рисунок 2.4.2 – Каскадная рекурсия

2.5 Удаленная рекурсия

Для демонстрации удаленной рекурсии была решена задача по нахождению функции Аккермана. Листинг кода программы представлен в приложении А.

Пример программы представлен на рисунке 2.5.1

Пример программы рисунок 2.5.1.

Результат работы программы приведен на рисунке 2.5.2.

Рисунок 2.5.2 –Удаленная рекурсия

3 Заключение

В результате выполнения лабораторной работы были закреплены знания, полученные на лекционных занятиях по дисциплине языки программирования, а также получены практические навыки по работы с рекурсивными функциями.

Отчет был написан согласно ГОСТ ОС ТУСУР.

Приложение А

(обязательное)

Листинг кода программы

# линенйная рекурсия (факториал)

def fact(x):

if x==1:

return 1

return fact(x-1)*x

print ("Факториал = " + str(fact(3)))

# повторная рекурсия (НОД)

def nod(x1, x2):

if x1*x2==0:

return max(x1, x2)

return nod(max(x1, x2) - min (x1, x2), min(x1, x2))

print("НОД = " + str(nod(180, 336)))

# взаимная рекурсия (Четность-Нечетность)

def chet(x):

if x==0:

return 'Четное'

return nechet(x-1)

def nechet(x):

if x==0:

return 'Нечетное'

return chet(x-1)

print("Четность-Нечетность = " + str(chet(6)))

# каскадная рекурсия (фибоначчи)

def fib(x):

if x==1:

return 0

if x==2:

return 1

return fib(x-1) + fib(x-2)

print("Фибоначчи = " + str(fib(10)))

# Удаленная рекурсия (функция Аккермана)

def akk(x, y):

if x==0:

return x+1

else:

if y==0:

return akk(x-1, 1)

else:

return akk(x-1, akk(x, y-1))

print("Функция Аккермана = " + str(akk(3, 6)))