Функции и замыкание

Пространства имён: повторение

Функции

Про рекурсию

Рекурсия в Python — это стек вызовов, см. пример

Гвидо, Python и хвостовой вызов

Замещение рекурсии стеком (не успеем)

TL;DR: см. ссылку выше: рекурсия это и есть стек.

TODO вынести в отдельную статью:

Разбор задачи. Есть ли среди натуральных чисел seq такие, что в сумме дают req?

Рекурсивный вариант:

Рекурсия — это цикл до исчерпания стека, содержащий как минимум три действия:

  1. Выполняется шаг рекурсии
  2. Если основание рекурсии не достигнуто, вычисляется и кладётся на стек новое значение связанных переменных (аналог рекурсивного вызова)
  3. Если основание рекурсии достигнуто, со стека снимаются связанные переменные 
       1 def subsS(seq, req):
   2     stack = [[req, -1]]                                 # Инициализация
   3     while stack:                                        # Цикл до исчерпания стека
   4         stack[-1][-1] += 1                              # Шаг рекурсии
   5         req, start = stack[-1]                          # (необязательное именование)
   6         if req == 0:                                    # Глобальное отсечение
   7             return True
   8         if start < len(seq) and req >= seq[start]:      # Основание не достигнуто и отсечение не сработало
   9             stack.append([req - seq[start], start])     # Рекурсивный вызов
  10         else:                                           # Основание рекурсии достигнуто
  11             stack.pop()                                 # Выход из рекурсивного вызова

    • Для удобства мы поименовали вершину стека как в рекурсивном варианте: req и start

Замыкание

Замыкание_(программирование)

  1. Функция — это объект
  2. Её можно изготовить внутри другой функции и вернуть
  3. …причём в зависимости от параметров этой другой функции!
  4. …в процессе чего некоторые объекты из ПИ создающей функции «залипают» в ПИ создаваемой
    • только они там навсегда должны залипнуть, а не только на время вызова

    • ⇒ .__closure__

  5. Это и есть замыкание!

Пример: 

   1 def f1(x):
   2     def f2():
   3         return x
   4     return f2

pythontutor this

и 

   1 def f1(x):
   2     def f2():
   3         def f3():
   4             return x
   5         return f3
   6     return f2

pythontutor this

Also: nonlocal name — явное указание брать имя name из внешнего, но не глобального пространства имён

Примеры: 1 и 2

Модификатор nonlocal для доступа к пространству имён вызывающей функции: 

   1 def f(x):
   2     def g(y):
   3         nonlocal x
   4         x = 5 * y - 3
   5     g(9)
   6     return x
   7 
   8 x = 100500
   9 res = f(x)
  10 print(x, res)

Замыкание и позднее связывание

Вот этот код не работает так, как может показаться: 

   1 def create_adders():
   2     adders = []
   3     for i in range(10):
   4         def adder(x):
   5             return i + x
   6         adders.append(adder)
   7     return adders
   8 
   9 for adder in create_adders():
  10     print(adder(1))

Выясняется, что все adder-ы работают одинаково — прибавляют 9!

Что происходит? 

   1 >>> c = create_adders()
   2 >>> c[1]
   3 <function create_adders.<locals>.adder at 0x7f272d2f93b0>
   4 >>> c[1].__closure__
   5 (<cell at 0x7f272d1c1510: int object at 0x7f272db36660>,)
   6 >>> c[2].__closure__
   7 (<cell at 0x7f272d1c1510: int object at 0x7f272db36660>,)
   8 >>> c[2].__closure__[0].cell_contents
   9 9
  10 >>> c[1].__closure__[0].cell_contents
  11 9
  12

По сути, в Python любое превращение имени в объект — это позднее связывание. Какой именно объект именуется i или x, каждый из adder-ов решает только когда его вызовут

Если мы хотели не этого, надо сделать так, чтобы при создании очередного adder-а его i именовало новый объект. Например, связывать это i отдельной переменной во время создания очередного adder-а: 

   1 def create_adders():
   2     adders = []
   3     for i in range(10):
   4         def adder(x, j=i):
   5             return j + x
   6         adders.append(adder)
   7     return adders

При этом никакого замыкания не произойдёт, у каждого adder-а будет своё локальное j, инициализированное соответствующим значением i. (Если бы нам нужно было сильнее запутаться, мы могли бы написать i=i вместо j=i ☺ ). 

   1 >>> c = create_adders()
   2 >>> c[1].__closure__
   3 >>> print(c[1].__closure__)
   4 None

Д/З

  1. Прочитать:

    • в Tutorial про функции

    • Про замыкания: Gabor Laszlo Hajba и Dmitry Soshnikov

    • Посмотреть, как оформлять задачи типа «написать функцию»

      • ВНИМАНИЕ! Первые три задания к этой лекции именно такого типа, последнее — обычное!

  2. EJudge: PatternSort 'Косортировка'

    Написать функцию pattsort(pattern, seq), которой передаются две последовательности одинаковой длины pattern и seq, причём все элементы pattern различны. Функция возвращает список элементов seq в порядке возрастания элементов pattern. То есть если наименьший элемент стоит в pattern на k-й позиции, то в выводе на k-й позиции должен стоять наименьший элемент seq, если второй минимум стоит в pattern стоит на позиции i, то второй минимум seq должен в выводе оказаться на позиции i и т. д.

    Input: 

       1 print(*pattsort((5, 4, 6, 3, 8, 1), (2, 2, 6, 1, 9, 6)))
    Output: 

    6 2 6 2 9 1

  3. EJudge: Without2Zeros 'Без двух нулей'

    Написать функцию No_2Zero(N, K), которая вычисляет количество N-значных чисел в системе счисления с основанием K, таких что их запись не содержит двух подряд идущих нулей. Лидирующие нули не допускаются. Для EJudge N⩽33.

    Input: 

    print(No_2Zero(6, 3))
    Output: 

    328

  4. EJudge: ArithFunct 'Арифметика функций'

    Написать четыре функции (функционала): ADD(f, g), SUB(f, g), MUL(f, g) и DIV(f, g), параметрами которых могут быть как обычные объекты, так и функции от одной переменной (проверить, является ли объект функцией можно с помощью callable(объект)). Возвращать эти функционалы должны функцию от одной переменной h(x), которая выполняет соответствующее действие — f(x)+g(x), f(x)-g(x), f(x)*g(x) или f(x)/g(x) — над этими переменными. Если f или g не были функцией, вместо f(x) используется f, а вместо g(x) — g (например, при умножении функции на константу).

    Input: 

       1 from math import *
   2 
   3 f = SUB(sin, cos)
   4 print(f(12), sin(12)-cos(12))
   5 
   6 g = DIV(sin, cos)
   7 print(g(pi/6), tan(pi/6))
   8 
   9 h = MUL(exp, 0.1)
  10 print(h(2), e**2/10)
  11 
  12 t = ADD(len, sum)
  13 print(t(range(5)))
    Output: 

    -1.380426876732927 -1.380426876732927
0.5773502691896256 0.5773502691896257
0.7389056098930651 0.738905609893065
15

  5. EJudge: AllProducts 'Разложения на сомножители'

    Ввести произвольное натуральное число, не превосходящее 1000000000, и вывести (через «*») все его разложения на натуральные сомножители, превосходящие 1, без учёта перестановок. Сомножители в каждом разложении и сами разложения (как последовательности) при выводе должны быть упорядочены по возрастанию. Само число также считается разложением. Можно использовать рекурсию.

    Input: 

    24
    Output: 

    2*2*2*3
2*2*6
2*3*4
2*12
3*8
4*6
24

LecturesCMC/PythonIntro2025/04_FunctionsClosure (последним исправлял пользователь FrBrGeorge 2025-09-30 20:59:42)