1. Лекция 3

5 октября 2018 года

Заметили ошибку или есть предложение? Напишите на почту: romansdidnotcrucify@gmail.com

$/!\$ ACHTUNG! WORK IN PROGRESS! $/!\$

Данная страница ещё не закончена и находится в процессе дополнения и переработки. Почитать уже можно, но не забудьте потом заглянуть, когда будет полная версия.

Содержание

Лекция 3
Алгебра логики
1. Что мы уже знаем
2. Логические операции
Условные операторы
Рекурсия

2. Алгебра логики

2.1. Что мы уже знаем

2.1.1. Тип bool

Давайте для начала вспомним, что мы вообще знаем про булевские (логические) значения в Python:

   1 >>> bool    # Мы знаем, что есть такой тип в питоне - bool
   2 <class 'bool'>
   3 >>> True    # У которого есть значения True
   4 True
   5 >>> type(True)
   6 <class 'bool'>
   7 >>> False    # И False
   8 False
   9 >>> type(False)
  10 <class 'bool'>
  11

2.1.2. Операции сравнения

Также помним, что есть операции сравнения, возвращающие булевские значения:

   1 >>>a, b = 10, 11
   2 >>> a<b    # Операция "меньше"
   3 True
   4 >>> a>b    # Операция "больше"
   5 False
   6 >>> a<=b    # Операция "меньше или равно"
   7 True
   8 >>> a>=b    # Операция "больше или равно"
   9 False
  10 >>> a==b    # Операция "равно"
  11 False
  12

2.1.3. Многоместные сравнения

Также вспоминаем, что в питоне есть многоместные сравнения. Причём не только в строго математическом стиле:

   1 >>>a,b,c,d=2,3,4,5
   2 >>> a < b < c < d    # Многоместное сравнение
   3 True
   4 >>> (a<b) and (b<c) and (c<d)    # на самом деле работает вот так (and - логическое "И", об этом ещё поговорим)
   5 True
   6 >>> a < b != c > d    # С математической точки зрения это выглядит, как минимум, странно
   7 False
   8 >>> (a<b) and (b != c) and (c > d)    # Но в питоне имеет вполне конкретный смысл
   9 False
  10 >>> a<b and b != c and c > d    # Скобочки можно было и не ставить; почему - поясню чуть позже
  11 False
  12

2.1.4. Операции is и in

Также в питоне есть операция сравнения is, которая проверяет, являются ли объекты одним и тем же объектом (это более сильное утверждение, чем просто равенство):

   1 >>> f=1,2,3    # Убедимся в этом на примере кортежей
   2 >>> g=1,2,3
   3 >>> f == g    # Объекты равны между собой
   4 True
   5 >>> f is g    # Но это два разных объекта
   6 False
   7 >>> f = g    # А теперь f и g будут ссылаться на один и тот же объект
   8 >>> f == g
   9 True
  10 >>> f
  11 (1, 2, 3)
  12 >>> f is g    # Что и продемонстрирует is
  13 True
  14

И ещё есть операция in, которая возвращает True, если элемент входит в последовательность:

   1 >>> 3 in (3,4,5)    # Содержится ли 3 в этом кортеже?
   2 True
   3 >>> 3 in (33,4,5)    # А в этом?
   4 False
   5

Собственно, названия is и in стоит понимать буквально, в том смысле, в каком они используются в английском языке.

2.1.4.1. WAT из прошлого года

В прошлом году я приводил пример смешной операции, который хорошо иллюстрирует, как работают многоместные операции сравнения в Python:

   1 >>> False is False    # Кстати, обратите внимание: и False, и True - это вполне конкретные объекты
   2 True
   3 >>> True in [False]    # Квадратными скобочками обозначается список - ещё одна структура данных в Python; о них поговорим позже, пока достаточно знать, что в данном случае это множество из одного элемента - False
   4 False
   5 >>> False is False in [False]    # Бессознательное нам подсказывает, что это False
   6 True
   7 >>> (False is False) in [False]    # Потому что видит данное выражение вот так
   8 False
   9 >>> (False is False) and (False in [False])    # Но, вспомнив, как работают многоместные операции сравнения, мы поймём, почему получили True
  10 True
  11

2.2. Логические операции

2.2.1. Над булевскими объектами

Алгебра логики, в простейшем случае, подразумевает наличие трёх операций:

"И", или логическое умножение, оно же конъюнкция;
"ИЛИ", или логическое сложение, оно же дизъюнкция;
"НЕ", или логическое отрицание, оно же инверсия (не путать с побитовой инверсией).

Все они есть в Python - соответственно, and, or и not:

   1 >>> False and False    # and
   2 False
   3 >>> False and True
   4 False
   5 >>> True and False
   6 False
   7 >>> True and True
   8 True
   9 >>> False or False    # or
  10 False
  11 >>> False or True
  12 True
  13 >>> True or False
  14 True
  15 >>> True or True
  16 True
  17 >>> not False    # not
  18 True
  19 >>> not True
  20 False
  21

То же самое - в виде таблицы истинности:

`or`			`and`			`not`
A	B	A `or` B	A	B	A `and` B	A	`not` A
`False`	`False`	`False`	`False`	`False`	`False`	`False`	`True`
`False`	`True`	`True`	`False`	`True`	`False`	`True`	`False`
`True`	`False`	`True`	`True`	`False`	`False`
`True`	`True`	`True`	`True`	`True`	`True`

2.2.2. Приоритет операций

В питоне выражения вычисляются с учётом следующего приоритета операций (данный список - неполный, и призван показать лишь один важный момент; полный список, в порядке возрастания приоритета, здесь):

группировка (выражения в скобках вычисляются первыми);
арифметические операции (внутри этой группы операций есть собственный приоритет - умножение/деление идёт раньше сложения/вычитания, например);
операции сравнения (они все одинаково приоритетны);
логические операции:
1. not
2. and
3. or

Это значит, что скобки для вычисления арифметических выражений перед логическими можно не ставить (во всех выше приведённых примерах, в частности). Этим питон выгодно отличается от, скажем, Паскаля.

При этом не забывайте, что операции в каждой из категорий также имеют разный приоритет.

   1 >>> a,b = 2,3
   2 >>> a+1>4 and b-2<3    # Порядок операций: арифметические -> сравнения -> логические
   3 False
   4 >>> a+1<4 or b-2<3
   5 True
   6 >>> a,b,c = True, False, False
   7 >>> a and b or c
   8 False
   9 >>> a or b and c    # У and приоритет выше, чем у or
  10 True
  11 >>> not b and a    # А у not - выше, чем у and
  12 True
  13

2.2.3. Логические операции над произвольными объектами

В питоне, как и в C/C++, логические операции могут выполняться не только над объектами типа bool, но и над объектами вообще.

2.2.3.1. Условные выражения

Для продолжения разговора обучимся сперва операции под названием "условное выражение". Это не условный оператор! (Хотя работает похоже.) Больше всего он похож на тернарный оператор в C/C++:

   1 >>> cond = True    # Пусть cond задаёт условие в нашем условном выражении
   2 >>> c = "QQ" if cond else "QKRQ!"    # Если условие имеет значение True (скоро мы увидим, что это не обязательно значит, что условие - булевская переменная или операция сравнения), вернуть то, что стоит перед if, иначе - вернуть то, что после else
   3 >>> c    # cond == True, поэтому получим "QQ"
   4 'QQ'
   5 >>> cond = False    # Поменяем условие на противоположное
   6 >>> c = "QQ" if cond else "QKRQ!"    # И снова воспользуемся условным выражением для вычисления c
   7 >>> c
   8 'QKRQ!'    # КУКАРЕКУ! Как и ожидалось
   9

2.2.3.2. Пустые объекты

В Python заимствован подход ещё из C, в котором изначально булевского типа не было, поэтому за False считался ноль, а за True - любое ненулевое число.

Гвидо, однако, пошёл дальше, и ввёл в язык понятие пустого объекта. Пустой объект эквивалентен False, а непустой - True. Причём пустой объект для каждого типа - один единственый, а вот непустых может быть сколько угодно:

   1 >>> False == 0    # К разговору о наследии C
   2 True
   3 >>> True == 1
   4 True
   5 >>> True + True    # Возможно даже такое
   6 2
   7 >>> cond = True    # Выражение, использующееся в качестве условия, может быть любого типа: 1. булевского
   8 >>> "Непустой" if cond else "Пустой"
   9 'Непустой'
  10 >>> cond = False    # Пустое значение типа bool
  11 >>> "Непустой" if cond else "Пустой"
  12 'Пустой'
  13 >>> "Непустой" if 100500 else "Пустой"    # 2. Численного (напоминаю, разделения на вещественные и целые в питоне нет)
  14 'Непустой'
  15 >>> "Непустой" if 0 else "Пустой"    # Пустое число
  16 'Пустой'
  17 >>> "Непустой" if "eggs & spam" else "Пустой"    # 3. Строкового
  18 'Непустой'
  19 >>> "Непустой" if "" else "Пустой"    # Пустая строка
  20 'Пустой'
  21 >>> "Непустой" if (1,2,3) else "Пустой"    # 4. Составного - кортеж, например
  22 'Непустой'
  23 >>> "Непустой" if () else "Пустой"    # Пустой кортеж
  24 'Пустой'
  25 >>> None    # Есть, кстати, специальное значение None, обозначающее пустой объект в общем
  26 >>> type(None)    # Для него есть целый отдельный тип
  27 <class 'NoneType'>
  28 >>> "Непустой" if None else "Пустой"    # И None, очевидно, является пустым объектом
  29 'Пустой'
  30 >>> "Непустой" if (None,) else "Пустой"    # При этом составные типы считаются непустыми, если они содержат вообще хоть что-нибудь - даже если это None; здесь - непустой кортеж
  31 'Непустой'
  32 >>> "Непустой" if print  else "Пустой"    # 5. Условие может даже иметь тип "функция", и т.д. и т.п.
  33 'Непустой'                                # Кстати, function - единственный тип, который я могу вспомнить (возможно, есть другие), у которого нет пустого объекта в принципе; любая функция (не результат вызова, а сама функция) эквивалентна True
  34 >>> print
  35 <built-in function print>
  36 >>> "Do not choose at all" if "evil 1" or "evil 2" else "Choose the least"    # Собственно, любой объект можно использовать не только в проверке условия, но и в логических операциях вообще
  37 'Do not choose at all'
  38

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

2.2.3.3. Зачем мы вводили условные выражения для проверки объекта на пустоту

Затем, что Гвидо пошёл ещё дальше, чем можно подумать: логические операции - and, or и not - вообще не обязаны возвращать True или False, они возвращают просто объект:

   1 >>> 'chair 1' or 'chair 2'    # Получим, внезапно, не булевское значение, а первый из объектов
   2 'chair 1'
   3 >>> 'chair 1' and 'chair 2'    # А здесь - второй (почему так - сейчас поясню)
   4 'chair 2'
   5

2.2.3.4. Ленивые вычисления в логических операциях

Посмотрим ещё раз на таблицу истинности для операций and и or:

`or`			`and`
A	B	A `or` B	A	B	A `and` B
`False`	`False`	`False`	`False`	`False`	`False`
`False`	`True`	`True`	`False`	`True`	`False`
`True`	`False`	`True`	`True`	`False`	`False`
`True`	`True`	`True`	`True`	`True`	`True`

Если присмотреться, можно увидеть, что, например, в or, если первый операнд истинный, второй можно вообще не вычислять - всё равно вернём True. Если же первый операнд ложный, второй всё-таки придётся вычислить.

В and - наоборот: если первый операнд ложный, второй можно не вычислять - всё равно вернём False. Если же первый операнд истинный, второй всё-таки придётся вычислить.

В питоне этим активно пользуются; таким образом, получим следующую таблицу возвращаемых логическими операциями значений (сравните с таблицей выше и убедитесь, что первая таблица - это то же самое, только для объектов конкретного, а именно булевского, типа):

`or`			`and`
A	B	A `or` B	A	B	A `and` B
Пустой	Пустой	B	Пустой	Пустой	A
Пустой	Непустой	B	Пустой	Непустой	A
Непустой	Пустой	A	Непустой	Пустой	B
Непустой	Непустой	A	Непустой	Непустой	B

Для закрепления понимания - ещё несколько примеров:

   1 >>> "Don't stop" and "me now"    # Придётся вычислить оба выражения; вернётся второй объект
   2 'me now'
   3 >>> (1,2,3,4,5) and 0    # Придётся вычислить оба выражения; вернётся второй объект
   4 0
   5 >>> "" and 10    # Достаточно вычислить первое выражение; вернётся первый объект
   6 ''
   7 >>> "" and 0    # Достаточно вычислить первое выражение; вернётся первый объект
   8 ''
   9 >>> "To be" or "not to be"    # Достаточно вычислить первое выражение; вернётся первый объект
  10 'To be'
  11 >>> "To be" or ""    # Достаточно вычислить первое выражение; вернётся первый объект
  12 'To be'
  13 >>> () or 42    # Придётся вычислить оба выражения; вернётся второй объект
  14 42
  15 >>> () or ""    # Придётся вычислить оба выражения; вернётся второй объект
  16 ''
  17

2.2.3.5. Опасность частичной вычислимости

Рассмотрим такой пример:

   1 >>> 23 and 1/0
   2 Traceback (most recent call last):
   3   File "<stdin>", line 1, in <module>
   4 ZeroDivisionError: division by zero

Результат закономерный. Но, если мы поставим вместо and or, это внезапно сработает:

   1 >>> 23 or 1/0
   2 23
   3

Почему так?

Мы вычислили первый операнд, поняли, что он True, а, значит, вычислять его не нужно. Синтаксически выражение верное, и, раз до вычисления второго выражения дело не дошло, этого достаточно, чтобы мы не получили ошибку.

Это ещё одна ситуация, в которой ошибка в коде есть, но мы её не увидим, пока не выполним код (а в данном случае нам должно попасться ещё и определённое значение левого операнда, чтобы вылезла ошибка). Лишнее подтверждение тому, насколько аккуратным нужно быть программисту при работе с интерпретируемым, а не компилируемым, языком.

При этом синтаксически неверные конструкции всё-таки приведут к ошибке сразу¹:

   1 >>> 23 or 1///0    # Вторую часть выражения мы бы не интерпретировали, если бы дошли до интерпретации - однако это синтаксическая ошибка, и она мешает начать выполнение программы
   2   File "<stdin>", line 1
   3     23 or 1///0
   4              ^
   5 SyntaxError: invalid syntax
   6 >>> dir()    # А теперь давайте напишем синтаксически верное выражение, использующее необъявленное имя
   7 ['__annotations__', '__builtins__', '__doc__', '__loader__', '__name__', '__package__', '__spec__', 'a', 'b', 'c', 'cond', 'd', 'f', 'fun', 'g', 'а']
   8 >>> 23 or some_variable_that_is_not_in_the_namespace    # И из-за ленивых вычислений ошибки не увидим
   9 23
  10 >>> 0 or some_variable_that_is_not_in_the_namespace    # А при других обстоятельствах могли бы
  11 Traceback (most recent call last):
  12   File "<stdin>", line 1, in <module>
  13 NameError: name 'some_variable_that_is_not_in_the_namespace' is not defined
  14 >>> 0 and 1/0    # Та же ситуация с and
  15 0
  16 >>> 42 and 1/0
  17 Traceback (most recent call last):
  18   File "<stdin>", line 1, in <module>
  19 ZeroDivisionError: division by zero

2.2.3.6. Частичная вычислимость в условном выражении

То же самое явление, связанное с ленивыми вычислениями, можно увидеть в условном выражении. Давайте смоделируем условное выражение с помощью логических операций²:

   1 >>> a, b = "QQ", "QKRQ!"    # Наши любимые "куку" и "кукареку"
   2 >>> cond = 5    # Условие, истинность которого будем проверять
   3 >>> a if cond else b    # Эта условная операция...
   4 'QQ'
   5 >>> cond and a or b    # ... в общем-то, эквивалентна этой
   6 'QQ'
   7 >>> cond = ()    # Сделаем так, чтобы cond было эквивалентно False
   8 >>> cond and a or b
   9 'QKRQ!'
  10

Всё бы хорошо, однако есть неприятная деталь: если a само по себе эквивалентно False, то приведённое выше выражение будет всегда возвращать b вне зависимости от значения проверяемого условия:

   1 >>> a = 0    # Пусть a эквивалентно False
   2 >>> cond = False    # Тогда, какое cond ни возьми, получим b
   3 >>> cond and a or b
   4 'QKRQ!'
   5 >>> cond = True
   6 >>> cond and a or b
   7 'QKRQ!'
   8

Словом, конструкция cond and a or b ненадёжная, пользуйтесь лучше a if cond else b.

Однако эта конструкция позволяет понять, как работает частичная вычислимость в условном выражении: если условие истинное, вычисляем только то, что стоит перед if; если ложное - только то, что после else:

   1 >>> cond = False    # Семантическая ошибка не проявит себя ни здесь
   2 >>> 10/0 if cond else "I feel danger nearby"
   3 'I feel danger nearby'
   4 >>> cond = True
   5 >>> dir()    # Ни здесь
   6 ['__annotations__', '__builtins__', '__doc__', '__loader__', '__name__', '__package__', '__spec__', 'a', 'b', 'c', 'cond', 'd', 'f', 'fun', 'g', 'а']
   7 >>> "Probably rats" if cond else another_variable_thats_not_there_and_will_break_your_production_code_someday
   8 'Probably rats'
   9 >>> cond = True    # А ошибка-то есть, просто требуется другое значение условия, чтобы она всплыла
  10 >>> 10/0 if cond else "I feel danger nearby"
  11 Traceback (most recent call last):
  12   File "<stdin>", line 1, in <module>
  13 ZeroDivisionError: division by zero
  14 >>> cond = False    # Здесь то же самое
  15 >>> "Probably rats" if cond else another_variable_thats_not_there_and_will_break_your_production_code_someday
  16 Traceback (most recent call last):
  17   File "<stdin>", line 1, in <module>
  18 NameError: name 'another_variable_thats_not_there_and_will_break_your_production_code_someday' is not defined
  19 >>> 10/0 if True else 3 /// 2    # Синтаксические ошибки при этом всё равно всплывают всегда
  20   File "<stdin>", line 1
  21     10/0 if True else 3 /// 2
  22                           ^
  23 SyntaxError: invalid syntax
  24 >>> 10/0 if True else 3 // 2    # Причём, обратите внимание, раньше, чем семантические (сравните с выражением выше)
  25 Traceback (most recent call last):
  26   File "<stdin>", line 1, in <module>
  27 ZeroDivisionError: division by zero

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

3. Условные операторы

3.1. Условный оператор

3.1.1. Простейший условный оператор

Условный оператор в Python выглядит очень просто: if, затем любое выражение, которое интерпретируется как пустое или непустое (т.е. условие), затем двоеточие, а на последующих строчках - блок с отступом в 4 пробела - тело оператора:

   1 >>> if 5:
   2 ...     print("QQ")    # Отступ в 4 пробела
   3 ...     print("QKRQ!")    # Блок может состоять как из одной, так и из большего числа строк
   4 ...    # Здесь отступа уже нет; в интерпретаторе просто жмём Enter, либо даже можем продолжить писать код (уже вне блока if) с этой строки
   5 QQ
   6 QKRQ!
   7 >>> if 5:    # Обратите внимание, что, если поставить неправильный отступ (не 4 пробела и не 0 пробелов), вылезет ошибка IndentationError, и код даже не будет интерпретироваться
   8 ...     print("I won't be printed because of indentation error")
   9 ...   print("I ruin everything")    # Делаем неправильный отступ
  10   File "<stdin>", line 3
  11     print("I ruin everything")
  12                              ^
  13 IndentationError: unindent does not match any outer indentation level    # И до интерпретации дело даже не доходит

3.1.2. else

Есть вторая часть условного оператора - else, которая соответствует блоку действий, которое нужно выполнить, если условие в if ложно:

   1 a, b, c = eval(input())    # Наша волшебная таблетка для ввода чисел через запятую
   2 
   3 if a >= b >= c:    # Проверим, что числа упорядочены по убыванию
   4     print("Упорядоченные")
   5 else:    # А если это не так, то
   6     print("Неупорядоченные")

   1 $ python3 -i upor1.py
   2 5,4,3
   3 Упорядоченные

   1 $ python3 -i upor1.py
   2 3,4,5
   3 Неупорядоченные

3.1.3. elif

И ещё между ними можно добавить сколько угодно блоков elif (от "else if"), каждый из которых нужно выполнить, если условие во всех предыдущих блоках было ложным, а в этом является истинным:

   1 a, b, c = eval(input())    # Восстановим справедливость! Некоторые числа упорядочены, но по возрастанию, как 3,4,5, например
   2 
   3 if a >= b >= c:    # Если это ложно
   4     print("Упорядочены")
   5 elif a <= b <= c:    # А это истинно
   6     print("Упорядочены по возрастанию")    # То сообщим, что числа всё же упорядочены
   7 else:
   8     print("Не упорядочены")

   1 $ python3 -i upor1.py     # Числа могут быть упорядочены по убыванию
   2 5,4,3
   3 Упорядочены

   1 $ python3 -i upor1.py    # Если это не так, они всё ещё могут быть упорядочены, но по возрастанию
   2 3,4,5
   3 Упорядочены по возрастанию

   1 $ python3 -i upor1.py    # А если уж и это не так, значит, они не упорядочены
   2 3,5,4
   3 Не упорядочены

При этом никакой магии в условном операторе в Python нет: условия блоков if и elif проверяются просто один за другим до первого истинного условия, иначе выполняется блок else. Поэтому проверки условий нужно располагать в правильном порядке - иначе можете получить не то, что ожидали:

   1 a, b, c = eval(input())
   2 
   3 if a >= b >= c:
   4     print("Упорядочены")
   5 elif a <= b <= c:
   6     print("Упорядочены по возрастанию")
   7 elif a == b == c:    # Этот блок недостижим: если условие a==b==c истинно, то истинно и a>=b>=c, которое находится раньше; тело данного блока не будет выполнено никогда
   8     print("Равны")
   9 else:
  10     print("Не упорядочены")

   1 $ python3 -i upor1.py    # В чём легко убедиться
   2 3,3,3
   3 Упорядочены

На самом деле, в данном примере следовало сделать так (и вообще, универсальное правило, которое мы ещё будем вспоминать: при проверке условий переходите от наиболее точных к наиболее общим, не наоборот):

   1 a, b, c = eval(input())
   2 
   3 if a == b == c:    # Вот теперь, если все три числа будут равны, мы это действительно увидим
   4     print("Равны")
   5 elif a >= b >= c:
   6     print("Упорядочены")
   7 elif a <= b <= c:
   8     print("Упорядочены по возрастанию")
   9 else:
  10     print("Не упорядочены")

   1 $ python3 -i upor1.py
   2 3,3,3
   3 Равны

3.2. Когда НЕ нужны elif и составные сравнения

Оператор elif, в общем-то, избыточен: его всегда можно заменить конструкцией из вложенных if-else:

   1 a, b, c = eval(input())    # Пример выше можно было записать и так
   2 
   3 if a == b == c:
   4     print("Равны")
   5 else:
   6     if a >= b >= c:
   7         print("Упорядочены")
   8     else
   9         if a <= b <= c:
  10             print("Упорядочены по возрастанию")
  11         else:
  12             print("Не упорядочены")

Зачем тогда нужен elif?

код становится короче;
лучше видно, где проверяемые условия являются равными между собой по значимости (a == b, a < b, a > b), а где мы хотим в случае выполнения одного условия проверить, истинно ли некоторое другое.

elif нужен для проверки однородных между собой условий; если же вы хотите копать глубже, т.е. вы уже проверили какое-то условие, оно истинно, и вы хотите разобрать подслучаи, вместо elif используйте вложенный условный оператор (то же самое касается составных условий):

   1 a, b, c = eval(input())    # Покажем, как можно раскрыть второй elif и составное сравнение в первом elif, чтобы решить немного другую задачу
   2                            # Пример получился довольно искусственный, но, поверьте, в реальном коде раскрывать if-else и составные сравнения
   3 if a == b == c:            # иногда приходится, и довольно подробно
   4     print("Равны")
   5 elif a >= b:    # Разбили условие a >= b >= c, т.е. a >= b and b >= c, на две части
   6     if b == c:    # И не ограничиваемся подслучаем b >= c, а проверяем различные варианты
   7         print("Упорядочены, причём b == c и a > b")
   8     elif b > c:
   9         print("Упорядочены")
  10     else:
  11         print("Не упорядочены, но a >= b")
  12 else:    # Пусть условие a >= b было для нас по каким-то причинам принципиально важным, поэтому всё, что соответствует a < b, выделяем в ветку else, а не просто ставим elif для случая a <= b <= c
  13     if a <= b <= c:
  14         print("Упорядочены по возрастанию")
  15     else:
  16         print("Не упорядочены")

3.3. И снова опасности частичной вычислимости

Как и в условном выражении, синтаксические ошибки в условном операторе будут обнаружены ещё до выполнения программы (объяснение того, почему, см. в примечаниях внизу страницы), а вот семантические, они же ошибки времени выполнения, до выполнения обнаружены не будут:

   1 cond = True    # Какое-нибудь условие, которое является истинным только в некоторых случаях; предположим, что сейчас оно истинно
   2 if cond and "enemies are nearby":
   3     print("You cannot fast travel")
   4 else:    # Если cond всегда будет True, мы никогда не узнаем, какой опасности подвергались
   5     printttttt("KILL ALL HUMANS", 1/0, mad_robots_from_outer_namespace)

   1 $ python3 -i upor1.py    # Кажется, программа хочет нам что-то сказать
   2 You cannot fast travel

   1 if True:
   2     print("Deeestroy everythhhing!")
   3 else:
   4     i = 0
   5     print("Stop right there, you criminal scum!", i++)    # Операции инкремента в python нет (ибо не нужна), поэтому i++ - синтаксическая ошибка

   1 $ python3 -i upor1.py    # А за синтаксические ошибки в Тамриэле отправляют в тюрьму, не разбираясь
   2   File "upor1.py", line 5
   3     print("Stop right there, you criminal scum!", i++)
   4                                                      ^
   5 SyntaxError: invalid syntax

4. Рекурсия

4.1. Циклы не нужны

Вообще говоря, для алгоритмически полного вычислительного формализма (и это дошло до меня только сегодня) достаточно трёх вещей:

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

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

4.2. Про синтаксический анализатор... Снова

Наверное, стоило просто выделить для этого отдельный раздел, поскольку эта тема поднимается уже третий раз за лекцию. [TODO?]

Поскольку весь код на питоне перед выполнением проходит через синтаксический анализатор (зачем - см. примечание внизу страницы), порядок определения функций в коде не важен, за исключением одной детали.

Если в коде объявлено несколько функций с одним и тем же именем, синтаксический анализатор не будет разбираться, что вы имели этим в виду (в питоне нет магии!); просто будет взято последнее из указанных определений функции.

Это так потому, что анализатор проходит по коду последовательно, и каждое последующее определение функции с одним и тем же именем попросту перезаписывает предыдущее, как перезаписываются переменные:

   1 a = 3    # Ровным счётом так же, как перезаписывается переменная
   2 a = "4"
   3 a = (5,10)
   4 
   5 def fun(a):    # Перезаписывается и определение функции
   6     print("Function 1")
   7 
   8 def fun(a, b):
   9     print("Function 2")
  10 
  11 def fun(a):    # Вот что будет вызываться при обращении к fun
  12     print("Function 3")

   1 $ python3 -i rec1.py
   2 >>> fun(1)    # Обратите внимание: третья функция перезаписала не только первую, с которой у неё совпал прототип
   3 Function 3
   4 >>> fun(1, 2)    # Но и вторую, у которой прототип был другой; поэтому полиморфизм в питоне организован иным, особым образом, о котором мы поговорим позже
   5 Traceback (most recent call last):
   6   File "<stdin>", line 1, in <module>
   7 TypeError: fun() takes 1 positional argument but 2 were given

4.3. Рекурсия в Python

В питоне рекурсия - это просто (прямой или непрямой) вызов функцией самой себя.

4.3.1. Стек вызовов

Вспоминаем, что происходит при вызове функции:

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

Приведём пример функций, которые друг друга вызывают:

   1 def fun0():    # Это у нас ещё пока не рекурсия
   2     fun1()
   3 
   4 def fun1():
   5     fun2()
   6 
   7 def fun2():
   8     fun3()
   9 
  10 def fun3():
  11     print("QQ")
  12 
  13 fun0()

   1 $ python3 -i rec1.py    # Пока ничего интересного
   2 QQ

Давайте теперь испортим код функции fun3, чтобы увидеть стек вызовов функций (traceback) и посмотреть на их вложенность:

   1 def fun0():
   2     fun1()
   3 
   4 def fun1():
   5     fun2()
   6 
   7 def fun2():
   8     fun3()
   9 
  10 def fun3():
  11     print("QQ", a)    # Невалидная операция: мы не объявляли имя "a"
  12 
  13 fun0()

   1 $ python3 -i rec1.py    # Читайте от последней строчки к первой: исключение возникло в функции fun3, вызванной в функции fun2, вызванной в fun1, вызванной в fun0, вызванной в строке 13 исходного кода
   2 Traceback (most recent call last):
   3   File "rec1.py", line 13, in <module>
   4     fun0()
   5   File "rec1.py", line 2, in fun0
   6     fun1()
   7   File "rec1.py", line 5, in fun1
   8     fun2()
   9   File "rec1.py", line 8, in fun2
  10     fun3()
  11   File "rec1.py", line 11, in fun3
  12     print("QQ", a)
  13 NameError: name 'a' is not defined
  14 >>>

Когда функция вызывает сама себя (т.е. при рекурсии), пространства имён, вложенные друг в друга, накапливаются точно так же, как в этом примере.

4.3.2. Глубина рекурсии

Давайте напишем простенькую функцию, вызывающую саму себя, и посмотрим, что произойдёт при её вызове:

   1 >>> def fun():    # Функция, которая ничего не делает, кроме как сама себя вызывает
   2 ...     fun()
   3 ...
   4 >>> fun()    # Мы организовали (актуально) бесконечную рекурсию, а т.к. ресурсы системы не бесконечны, в конечном счёте получим ошибку
   5 Traceback (most recent call last):
   6   File "<stdin>", line 1, in <module>
   7   File "<stdin>", line 2, in fun
   8   File "<stdin>", line 2, in fun
   9   File "<stdin>", line 2, in fun
  10   [Previous line repeated 995 more times]
  11 RecursionError: maximum recursion depth exceeded

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

Давайте напишем какую-нибудь более интересную функцию; пусть она, например, посчитает нам, сколько же раз функция сама себя вызвала:

   1 >>> count = 0    # Это будет наш счётчик
   2 >>> def fun():
   3 ...     global count    # Не забываем про то, что если не указать явно, что мы используем глобальную переменную,
   4 ...     count += 1      # то для выполнения операции связывания будет создана локальная переменная, и мы не сможем ничего посчитать
   5 ...     fun()
   6 ...
   7 >>> fun()
   8 Traceback (most recent call last):
   9   File "<stdin>", line 1, in <module>
  10   File "<stdin>", line 4, in fun
  11   File "<stdin>", line 4, in fun
  12   File "<stdin>", line 4, in fun
  13   [Previous line repeated 995 more times]
  14 RecursionError: maximum recursion depth exceeded
  15 >>> count    # Проверяем, чего насчитали (хотя, кто внимательно читает, уже из предыдущего примера увидел, сколько вызовов может произойти)
  16 999
  17

На самом деле, глубина стека вызовов несколько больше, однако мы с вами уже находимся на некоторой глубине стека (если запустите код выше через IDLE, увидите, что было сделано ещё меньше вызовов, поскольку сам IDLE тоже требует нескольких уровней вложенных вызовов).

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

4.3.3. Остановка рекурсии

Если хотите, чтобы рекурсия когда-нибудь остановилась - не забудьте организовать для этого условия.

Давайте реализуем простейший счётчик, чтобы понять, когда остановиться:

   1 def fun(n):    # n - счётчик
   2     print(n)    # Это чтобы видеть, где мы находимся
   3     if n:    # Пока n не равно нулю, вызвать себя ещё раз, но передав счётчик, меньший на единицу
   4         fun(n-1)
   5 
   6 fun(10)    # Для примера вызовем нашу функцию от 10

   1 $ python3 -i rec1.py    # Довольно симпатично; правда, получилось 11 чисел вместо 10 из-за того, что печать числа происходит перед проверкой счётчика
   2 10
   3 9
   4 8
   5 7
   6 6
   7 5
   8 4
   9 3
  10 2
  11 1
  12 0

Правда, у этой реализации есть один важный недостаток: рекурсия не останавливается, как нужно, если n - отрицательное:

   1 $ python3 -i rec1.py
   2 10
   3 9
   4 8
   5 7
   6 6
   7 5
   8 4
   9 3
  10 2
  11 1
  12 0
  13 >>> fun(-12)
  14 -12
  15 -13
  16 -14
  17 # Пропускаем много-много строк вывода
  18 -1005
  19 -1006
  20 -1007
  21 Traceback (most recent call last):
  22   File "<stdin>", line 1, in <module>
  23   File "rec1.py", line 4, in fun
  24     fun(n-1)
  25   File "rec1.py", line 4, in fun
  26     fun(n-1)
  27   File "rec1.py", line 4, in fun
  28     fun(n-1)
  29   [Previous line repeated 992 more times]
  30   File "rec1.py", line 2, in fun
  31     print(n)
  32 RecursionError: maximum recursion depth exceeded while calling a Python object
  33 -1008
  34

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

Пример выше очень легко исправить (кстати, почти универсальное правило: задавать точное значение как условие выхода - ненадёжно, задавайте диапазон):

   1 def fun(n):
   2     if n > 0:    # Гениально простой фикс
   3         print(n)    # И давайте заодно не будем печатать счётчик при n <= 0
   4         fun(n-1)
   5 
   6 fun(10)

   1 $ python3 -i rec1.py
   2 10
   3 9
   4 8
   5 7
   6 6
   7 5
   8 4
   9 3
  10 2
  11 1
  12 >>> fun(-12)    # Ура, больше никакого исчерпания стека вызовов
  13 >>>

Кстати, мы печатали числа в обратном порядке, а могли бы и в прямом:

   1 def fun(n):
   2     if n > 0:
   3         fun(n-1)
   4         print(n)    # Теперь печать будет выполняться только после того, как стек вложенных вызовов свернётся обратно, т.е. первой печатать будет функция, находящаяся максимально глубоко
   5 
   6 fun(10)

   1 python -i rec1.py
   2 1
   3 2
   4 3
   5 4
   6 5
   7 6
   8 7
   9 8
  10 9
  11 10

4.3.4. Гвидо и хвостовая рекурсия

To be continued...

Забегая вперёд: это происходит потому, что код всей программы на питоне перед выполнением сначала превращается во что-то вроде байткода. Синтаксически неверную конструкцию нельзя разобрать и превратить в байткод, поэтому такие ошибки сразу всплывают. А вот что-то семантически некорректное - например, деление на ноль или использование необъявленного имени в вычислении выражения - будет видно, только если интерпретатор дойдёт во время выполнения до данного места. (1)
Это такой "хакерский" способ, он использовался в первом питоне и даже в ранних версиях второго. (2)

LecturesCMC/PythonIntro2018/03_ConditionalsRecursion/Conspect (последним исправлял пользователь RomanKrivonogov 2018-10-08 12:11:09)