Lesson 8
Функции и рекурсия
1. функции
Напомним, что в математике факториал числа n определяется как
# вычислить 3!
res = 1
for i in range(1, 4):
res *= i
print(res)
# вычислить 5!
res = 1
for i in range(1, 6):
res *= i
print(res)
Однако, если мы допустим ошибку в исходном коде, этот ошибочный код появится во всех местах, где мы скопировали вычисление факториала. Более того, код длиннее, чем может быть. Чтобы избежать повторной записи той же логики в языках программирования, существуют функции.
Функции - это секции кода, которые изолированы от остальной части программы и выполняются только при вызове. Вы уже встретили функции sqrt() , len() и print() . Все они имеют что-то общее: они могут принимать параметры (ноль, один или несколько из них), и они могут возвращать значение (хотя они могут и не возвращаться). Например, функция sqrt() принимает один параметр и возвращает значение (квадратный корень из заданного числа). Функция print() может принимать различное количество аргументов и ничего не возвращает.
Теперь мы хотим показать вам, как написать функцию factorial() которая принимает один параметр - число и возвращает значение - факториал этого числа.
def factorial(n):
res = 1
for i in range(1, n + 1):
res *= i
return res
print(factorial(3))
print(factorial(5))
Мы хотим дать несколько объяснений. Во-первых, код функции должен быть помещен в начало программы (до места, где мы хотим использовать функцию factorial() , если быть точным). Первая строка def factorial(n): из этого примера является описанием нашей функции; слово factorial является идентификатором (имя нашей функции). Сразу после идентификатора появляется список параметров, которые получает наша функция (в скобках). Список состоит из разделенных запятыми идентификаторов параметров; в нашем случае список состоит из одного параметра n . В конце строки поместите двоеточие.
Затем идет тело функции. В Python тело должно быть отступом (по Tab или четыре пробела, как всегда). Эта функция вычисляет значение n! и сохраняет его в переменной res . Последней строкой функции является return res , которая выходит из функции и возвращает значение переменной res .
Оператор return может отображаться в любом месте функции. Его выполнение завершает функцию и возвращает указанное значение в место, где была вызвана функция. Если функция не возвращает значение, оператор return фактически не возвращает какое-либо значение (хотя оно все еще может быть использовано). Некоторым функциям не нужно возвращать значения, и оператор return может быть опущен для них.
Мы хотели бы привести еще один пример. Вот функция max() которая принимает два числа и возвращает максимум из них (на самом деле эта функция уже стала частью синтаксиса Python).
def max(a, b):
if a > b:
return a
else:
return b
print(max(3, 5))
print(max(5, 3))
print(max(int(input()), int(input())))
Теперь вы можете написать функцию max3() которая принимает три числа и возвращает максимум из них.
def max(a, b):
if a > b:
return a
else:
return b
def max3(a, b, c):
return max(max(a, b), c)
print(max3(3, 5, 4))
Встроенная функция max() в Python может принимать различное количество аргументов и возвращать максимум из них. Вот пример того, как можно написать такую функцию.
def max(*a):
res = a[0]
for val in a[1:]:
if val > res:
res = val
return res
print(max(3, 5, 4))
a , который обозначен звездочкой.
2. Локальные и глобальные переменные
Внутри функции вы можете использовать переменные, объявленные где-то вне нее:
def f():
print(a)
a = 1
f()
Здесь переменная a установлена в 1, а функция f() печатает это значение, несмотря на то, что когда мы объявляем функцию f эта переменная не инициализируется. Причина в том, что во время вызова функции f() (последняя строка) переменная a уже имеет значение. Вот почему функция f() может отображать ее.
Такие переменные (объявленные вне функции, но доступные внутри функции) называются глобальными .
Но если вы инициализируете некоторую переменную внутри функции, вы не сможете использовать эту переменную за ее пределами. Например:
def f():
a = 1
f()
print(a)
Мы получаем ошибку NameError: name 'a' is not defined . Такие переменные, объявленные внутри функции, называются локальными . После выхода из функции они становятся недоступными.
Что действительно очаровательно здесь, что произойдет, если вы измените значение глобальной переменной внутри функции:
def f():
a = 1
print(a)
a = 0
f()
print(a)
Эта программа напечатает вам числа 1 и 0. Несмотря на то, что значение переменной a измененное внутри функции, вне функции остается неизменным! Это делается для того, чтобы «защитить» глобальные переменные от непреднамеренных изменений функции. Итак, если какая-либо переменная изменяется внутри функции, переменная становится локальной переменной, и ее модификация не изменит глобальную переменную с тем же именем.
Более формально: интерпретатор Python рассматривает переменную локальную для функции, если в коде этой функции есть хотя бы одна команда, которая изменяет значение переменной. Тогда эта переменная также не может быть использована до инициализации. Инструкции, которые изменяют значение переменной - operator = , += и использование переменной в качестве цикла for параметра. Однако, даже если оператор change-variable никогда не выполняется, интерпретатор не может его проверить, и переменная остается локальной. Пример:
def f():
print(a)
if False:
a = 0
a = 1
f()
Произошла ошибка: UnboundLocalError: local variable 'a' referenced before assignment . А именно, в функции f() идентификатор a становится локальной переменной, так как функция содержит команду, которая модифицирует переменную a . Инструкция по модификации никогда не будет выполнена, но интерпретатор не проверяет ее. Поэтому, когда вы пытаетесь распечатать переменную a , вы обращаетесь к неинициализированной локальной переменной.
Если вы хотите, чтобы функция могла изменять какую-либо переменную, вы должны объявить эту переменную внутри функции, используя ключевое слово global :
def f():
global a
a = 1
print(a)
a = 0
f()
print(a)
В этом примере будет напечатан вывод 1 1, потому что переменная a объявлена глобальной, а ее изменение внутри функции вызывает ее изменение в глобальном масштабе.
Однако лучше не изменять значения глобальных переменных внутри функции. Если ваша функция должна изменить некоторую переменную, пусть она вернет это значение, и вы выберете при вызове функции явно назначить переменную этому значению. Если вы следуете этим правилам, логика функций работает независимо от логики кода, и поэтому такие функции могут быть легко скопированы из одной программы в другую, экономя ваше время.
Например, предположим, что ваша программа должна вычислить факториал данного номера, который вы хотите сохранить в переменной f. Вот как вы не должны этого делать:
def factorial(n):
global f
res = 1
for i in range(2, n + 1):
res *= i
f = res
n = int(input())
factorial(n)
print(f)
# делать другие вещи с переменной f
Это пример плохого кода, потому что трудно использовать другое время. Если завтра вам понадобится другая программа для использования функции «factorial», вы не сможете просто скопировать эту функцию и вставить новую программу. Вам нужно будет убедиться, что эта программа не содержит переменную f .
Гораздо лучше переписать этот пример следующим образом:
# начало фрагмента кода, который можно скопировать из программы в программу
def factorial(n):
res = 1
for i in range(2, n + 1):
res *= i
return res
# конец фрагмента кода
n = int(input())
f = factorial(n)
print(f)
# делать другие вещи с переменной f
Полезно сказать, что функции могут возвращать более одного значения. Вот пример возврата списка из двух или более значений:
return [a, b]
Вы можете вызвать функцию такого списка и использовать его в нескольких назначениях:
n, m = f(a, b)
3. Рекурсия
Как мы видели выше, функция может вызвать другую функцию. Но функции могут также называть себя! Чтобы проиллюстрировать это, рассмотрим пример факторно-вычислительной функции. Хорошо известно, что 0! = 1, 1! = 1. Как рассчитать значение n! для больших n? Если бы нам удалось вычислить значение (n-1) !, то мы легко вычислим n !, так как n! = N⋅ (n-1) !. Но как вычислить (n-1) !? Если мы вычислили (n-2) !, тогда (n-1)! = (N-1) ⋅ (n-2) !. Как рассчитать (n-2) !? Если ... В итоге мы получаем 0 !, что равно 1. Таким образом, для вычисления факториала мы можем использовать значение факториала для меньшего целого числа. Этот расчет можно сделать с помощью Python:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
print(factorial(5))
Ситуация, когда функция вызывает себя, называется рекурсией , и такая функция называется рекурсивной.
Рекурсивные функции - мощный механизм программирования. К сожалению, они не всегда эффективны и часто приводят к ошибкам. Наиболее распространенной ошибкой является бесконечная рекурсия , когда цепочка вызовов функций никогда не заканчивается (ну, на самом деле, она заканчивается, когда у вас заканчивается свободная память на вашем компьютере). Пример бесконечной рекурсии:
def f():
return f()
Две наиболее распространенные причины, вызывающие бесконечную рекурсию: - Неправильное условие остановки. Например, если в факториал-калькуляционной программе мы забываем поставить проверку,
if n == 0, тоfactorial(0)вызоветfactorial(-1), который вызоветfactorial(-2)и т. Д. - Рекурсивный вызов с неправильными параметрами. Например, если функция
factorial(n)вызывает функциюfactorial(n), мы также получим бесконечную цепочку вызовов.
Поэтому при кодировании рекурсивной функции сначала необходимо убедиться, что она достигнет своих условий остановки - подумать, почему ваша рекурсия когда-либо закончится.