Информатика

Функции и рекурсия

4.5.2022

5721

На этой странице вы узнаете

Как функция поможет нам упростить алгоритм нарезки овощей?
Как переменные играют в прятки?
Чем опасна неправильно описанная матрешка?

Утром мы чистим зубы. Мало кто разбивает этот процесс на отдельные действия: включить воду, намочить щетку, выдавить зубную пасту… Мы называем это просто «почистить зубы». И в этом больше связи с информатикой, чем кажется на первый взгляд.

Определение функции

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

Предлагаем сразу разобрать на примере.

Помните, когда мы только начали изучать алгоритмы, мы готовили супчик? Подробнее о том, как мы это делали, можно прочитать в статье «Основы алгоритмов». Давайте вспомним этот алгоритм и уделим особое внимание первому пункту.

Что значит «нарезать овощи»? Сколько их у нас, какие конкретно надо нарезать, да и как вообще резать овощи?

Нарезка овощей – это полноценный отдельный алгоритм. Распишем его подробно.

Будем честны — выглядит так себе. Это фактически одинаковые части алгоритма, которые применяются к разным овощам. А если мы добавим в суп еще больше овощей, нам придется для каждого продукта внедрять эту же часть алгоритма, меняя только название овоща. Здесь нам на помощь и приходит функция.

Как функция поможет нам упростить алгоритм нарезки овощей?

У нас есть блок кода, который применяется многократно, пусть и к разным объектам. Мы можем «вырезать» его из алгоритма и дать ему какое-то имя. Когда этот блок понадобится, мы «позовем» его и скажем, с чем именно нужно проделать операции.

Так, в алгоритме нарезки овощей можно выделить функцию «нарезать (овощ)».

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

Реализация функции в Python

На языке Python структура записи функции выглядит так:

def <имя функции>(<аргументы>):
<тело функции>

Здесь <тело функции> будет тем самым блоком кода, который мы сможем вызывать по <имени функции>. Ему мы будем передавать <аргументы>, использующиеся в функции.

Аргументов может быть:

множество, тогда они прописываются через запятую;
он может быть один;
может их и не быть, тогда нужно будет оставить пустые скобки.

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

Как переменные играют в прятки?

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

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

def sq(a):
a = a ** 2

a = 5
sq(a)
print(a)

Мы написали функцию, которая принимает значение a, возводит его в квадрат через оператор ** и записывает результат в себя же.

Вывод: 5

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

Одна а — это параметр функции sq, изменяемый внутри нее. Ее область видимости — функция sq, за ее пределами об a ничего не известно.
Другая а — это переменная, хранимая в основной части кода. Ее область видимости, наоборот, лежит за пределами метода sq. Эта переменная ни разу не менялась и поэтому на экран было выведено ее первоначальное значение.

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

Значение, указанное после return, будет «вброшено» в программу. Его можно будет «поймать», например, передав это значение переменной или функции вывода на экран.

При этом команда return действует на функцию точно так же, как команда break на цикл: она моментально прекращает работу и продолжает выполнение основного кода программы.

def sq(a):
    a = a ** 2
    return a
    print(“Эта фраза не будет напечатана”)

a = 5
a = sq(a)
print(a)

Теперь, после возведения числа в квадрат функция возвращает его, благодаря чему мы можем получить это значение в основном блоке программы.
Но команда print после return уже не будет выполнена, так как return останавливает работу функции после сообщения основному коду значения a.

Вывод: 25

Все получилось так, как мы и ожидали: print после return не был выполнен, а значение переменной a поменялось.

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

def sq(a, b): a = a 2 b = b 2 return a, b a = 5 b = 10 a, b = sq(a, b) print(a, b)	def sq(a, b): a = a 2 b = b 2 return a, b a = 5 b = 10 x = sq(a, b) print(x)
Вывод: 25 100	Вывод: (25, 100)
Кортеж, возвращенный функцией sq, был разбит на составляющие, записанные в a и b.	Кортеж, возвращенный от sq, был записан целиком в одну переменную.

Команда return также может быть не одна в функции, например, при использовании условной конструкции. Тогда сработает только та команда return, которая выполнится раньше.

Имена переданных переменных не обязаны совпадать с именами аргументов, ведь в функции создаются копии этих переменных.

Например, в приведенной ниже функции:

значение переменной start будет равно значению переменной a;
значение end будет равно b;
значение number — 25.

Все данные будут переданы в указанном порядке.

Наконец, команды return может в принципе не быть в функции, если нам не нужно сохранять результат ее работы. Это может быть в случае, если мы хотим лишь вывести итог на экран. Тогда вместо return прямо в функции можно использовать команду print и вызывать ее без присвоения данных.

def sq(a, b):
    a = a ** 2
    b = b ** 2
    print(a, b)

a = 5
b = 10
sq(a, b)

Вывод: 25 100

Здесь мы сделали вывод внутри функции sq, поэтому на экран выведены уже измененные в процессе работы sq значения a, b.

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

def sq(a): return a ** 2 def add_two(a): return a + 2 def add_two_and_sq(a): return sq(add_two(a)) a = 5 print(add_two_and_sq(a))	В функции add_two_and_sq сначала будет вычислен аргумент для sq — add_two(a), который затем будет возведен в квадрат функцией sq. Таким образом, эта функция по числу a находит (a+2)².
Вывод: 49

Но и это не самый интересный способ применения функций, можно с ними делать еще более мощные приемы.

Определение и реализация рекурсии

Рекурсия — это функция, которая вызывает саму себя.

Идеальный пример рекурсии — матрешка. По сути, матрешка — это:

Кукла, в которой сидит:
- кукла, в которой сидит:
  - кукла, в которой сидит:
    - кукла, в которой сидит…

Чем опасна неправильно описанная матрешка?

Матрешка могла бы стать эталоном бесконечной зацикленности. Мы открываем матрешку, внутри нее матрешка. Мы снова открываем матрешку, внутри нее матрешка. Мы снова открываем матрешку, внутри нее матрешка. В итоге всю свою жизнь мы будем открывать матрешки — не самое интересное занятие, не так ли?
Если бы не самая маленькая матрешка! Рано или поздно в этой беспощадной кукле мы найдем последнюю, неделимую, которая прервет череду повторяющихся действий, и мы сможем пойти заниматься другими делами.

Вызывая функцию внутри самой себя, каждый раз мы открываем новую матрешку. Главное — создать то самое действие, которое завершит все предыдущие — условие остановки.

Хороший пример реализации рекурсивной функции — нахождение факториала числа n. Напомним, факториал числа n — это произведение всех целых чисел от 1 до n:
\(n!=1 *2*3 …*n-1*n\).

Рекурсия здесь заключается в том, что для нахождения факториала n мы число n умножаем на произведение всех чисел до него, то есть от 1 до n-1. А это не что иное, как факториал n-1.

n! = n * (n-1)!

То есть, чтобы найти факториал числа, надо найти факториал числа поменьше.

Условием остановки будет число 1. Мы заранее знаем, что 1! = 1, и на этом и будем останавливаться.

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n — 1)

print(factorial(5))

Вывод: 120

Чтобы полностью понять работу рекурсии, давайте проделаем все те же операции, что она делает, и найдем факториал от 5:

Чтобы найти 5!, надо 5 умножить на 4!.
Чтобы найти 4!, надо 4 умножить на 3!.
Уменьшение искомого факториала будет происходить до тех пор, пока мы не дойдем до известного условия остановки. Незавершенные вычисления так и останутся незавершенными, ожидая, что мы найдем необходимые для них значения.
Когда перед нами появится задача найти 1!, мы выполним ее моментально: узнаем конкретное значение и передадим его выше по рекурсии.
Зная это значение, мы сможем вычислить еще одно – факториал от 2, который будет равен 2 * 1! – и также поднять его выше по рекурсии.
Рано или поздно мы поднимемся на самый верх, найдя самое первое искомое значение.

В программе каждое такое промежуточное вычисление остается «подвешенным» и ожидает выполнения последующих операций, продолжая занимать выделенные на себя ресурсы. Если глубина рекурсии станет слишком большой, программа просто не сможет забраться так глубоко и выдаст нам ошибку “RecursionError: maximum recursion depth exceeded in comparison” – буквально «ошибка рекурсии: достигнута максимально допустимая глубина рекурсии».

В каких случаях это может возникнуть?

Ошибка в записи условия остановки или вовсе его отсутствие. Если мы сами никак не завершим работу рекурсии, за нас это сделает ошибка.

Сильная наглость. Например, написанная нами выше программа не сможет найти факториал от 1000, потому что ей придется подключить 1000 рекурсий. Это уже проблема, которую мы решим отдельно в статье «Динамический подход к решению задач».

Практика

Функции — это одно из самых основных понятий программирования, так что применять их можно в огромном количестве задач на ЕГЭ и ОГЭ. Так, понимание работы рекурсии необходимо для решения задач 16 и 23 ЕГЭ, но она также может быть применена и в других более редких случаях, например, в задаче 8 ЕГЭ.

Сейчас мы с вами для примера разберем логику решения номера 16 ЕГЭ.

Условие задачи:

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

F(1) = 1;
F(n) = n + 5 * F(n — 2), если n — нечетно и n > 1;
F(n) = 2 * n * F(n — 1), если n — четно и n > 1.

Чему равно значение функции F(9)? В ответе запишите только целое число.

Решение.

1. Первым делом нужно создать функцию F(n) с помощью def F(n).

2. В функции пропишем три условия. Каждое из условий будет описывать одно соотношение из условия задачи с помощью кода. Получим следующие участки кода:

Для F(1) = 1:

if n == 1:
return 1

Для F(n) = n + 5 * F(n — 2), если n — нечетно и n > 1 создадим условие if, которое будет срабатывать только для нечетных n, если они больше 1. Для этого условия опишем математическое выражение, которое должна вернуть функция. Получится следующий код:

if n % 2 != 0 and n > 1:
return n + 5 * F(n — 2)

Для F(n) = 2 * n * F(n — 1), если n — четно и n > 1 построим код аналогично предыдущему пункту и получим последнюю ветку функции:

if n % 2 == 0 and n > 1:
return 2 * n * F(n — 1)

3. После описания функции остается только вывести значение функции F(9) через print, что и будет ответом.

Полный код программы:

def F(n):
if n == 1:
return 1
if n % 2 != 0 and n > 1:
return n + 5 * F(n — 2)
if n % 2 == 0 and n > 1:
return 2 * n * F(n — 1)

print(F(9))

Запустим получившуюся программу, она выведет нам число 1169. Это и есть ответ.

Ответ: 1169

Функции — это очень полезный инструмент для решения задач на ЕГЭ. Но в дальнейшей работе этот инструмент становится просто незаменим, потому что с повторным использованием одних и тех же алгоритмов программисты сталкиваются постоянно. А узнать еще больше про эффективные способы применения функций можно в нашей статье «Практика работы с функциями».

Термины

Команда break — команда, прерывающая выполнение цикла.

Кортеж — структура данных, схожая по функционалу со списком, но неизменяемая после создания. К кортежу неприменимы команды append и remove. Вспомнить про кортеж подробнее можно в статье «Практика работы с массивами».

Натуральные числа — это числа, возникающие естественным образом при счете: 1, 2, 3, 4, 5, 6, 7 и так далее.

Переменная — это ячейка в памяти компьютера, которая хранит имя и определенное значение: например, число или какой-то текст.

Условная конструкция — часть программы, которая выполняет разные участки кода в зависимости от состояния программы.

Цикл (циклическая операция) — это многократное повторение определенной команды или набора команд. Для выделения тела цикла используется табуляция.

Фактчек

Функции используются для более короткой записи кода и его структуризации за счет вынесения повторяющихся блоков кода.
Функции в Python создаются командой def, возвращают результат работы командой return.
Функция может использоваться и вызываться в любом другом месте кода неограниченное количество раз.
В рекурсии очень важным элементом является условие остановки. Без него работа рекурсии не сможет быть выполнена до конца.

Проверь себя

Задание 1.
Сколько аргументов может передаваться функции изначально?

Только один.
Сколько необходимо, но минимум – один.
Сколько необходимо, в том числе 0.
Функции не нужны аргументы.

Задание 2.
Без запуска кода выясните, что будет выведено на экран в результате работы следующего кода.

def f(a, b, c):
    a **= 2
    b *= 3
    return a + b * c
    return a * b + c
print(f(1, 2, 3))

19
9
(19, 9)
такая запись невозможна

Задание 3.
В чем заключается принцип работы рекурсии?

Разовый вызов функции.
Несколько возвращаемых значений.
Многократный вызов функции из основного кода.
Функция вызывает сама себя.

Задание 4.
При выводе программой ошибки «RecursionError: maximum recursion depth exceeded in comparison» нужно…

Паниковать.
Перепроверить аргументы функции.
Перепроверить возвращаемые аргументы.
Перепроверить условие остановки рекурсии.

Ответы: 1. — 3; 2. — 1; 3. — 4; 4. — 4.

Информатика Рекурсия Функции

Понравилась статья? Оцени: