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

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

Функции

Про рекурсию

Рекурсия в 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. Прочитать:

  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: BinPow 'Бинарное возведение в степень'

    Написать функцию BinPow(), которая принимает три параметра: python3-объект a, натуральное число 0<N<1000000, и некоторую ассоциативную бинарную функцию f(). Функция BinPow() реализует алгоритм бинарного возведения в степень (кроме нулевой степени). Результатом BinPow(a, n, f) будет применение f(x) к a n-1 раз.

    Input: 

       1 print(BinPow(2, 33, lambda a, b: a * b), 2**33)
   2 print(BinPow("Se", 7, str.__add__))
    Output: 

    8589934592 8589934592
SeSeSeSeSeSeSe

  4. EJudge: Det4x4 'Определитель матрицы 4×4'

    Матрица 4×4 задаётся кортежем из 4 кортежей по 4 целых числа в каждом. Написать функцию det4(r0, r1, r2, r3), вычисляющую точный определитель матрицы (r0, r1, r2, r3). Пользоваться itertools нельзя. Числа содержат не более 66666 десятичных знаков.

    Input: 

    print(det4((5, -4, 4, -7), (1, -2, 6, 0), (3, -8, -6, -4), (-1, 2, -9, 3)))
    Output: 

    702

  5. EJudge: MaxFun 'Функция побольше'

    Написать функцию maxfun(), которая принимает переменное число параметров — числовую последовательность S, функцию F1 и, возможно, ещё несколько функций F2 … Fn. Возвращает она ту из функций Fi, сумма значений которой на всех элементах S наибольшая. Если таких функций больше одной, возвращается Fi с наибольшим i.

    Input: 

    from math import *
print(maxfun(range(-2,10), sin, cos, exp)(1))
    Output: 

    2.718281828459045

LecturesCMC/PythonIntro2026/04_FunctionsClosure (последним исправлял пользователь FrBrGeorge 2026-10-07 23:06:02)