Функциональное программирование

Функция, которая принимает одну или несколько функций как аргументы и/или возвращает функцию. Это возможно, потому что в Python функции — объекты первого класса. Примеры: map, filter, sorted(key=...) и декораторы.

map(f, seq) применяет f к каждому элементу; filter(pred, seq) оставляет элементы, где pred истинно, — оба возвращают ленивые итераторы в Python 3. reduce(f, seq[, init]) из functools сворачивает последовательность в одно значение.

Парадигма, трактующая вычисление как применение функций и предпочитающая чистые функции и неизменяемость изменяемому состоянию. Python поддерживает её частично: функции первого класса, lambda, comprehensions, functools.

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

Ленивые, экономные по памяти строительные блоки для итераторов. count, cycle и repeat бесконечны; chain склеивает итерируемые; islice лениво режет без материализации; groupby, product и combinations дают группировку и комбинаторику. Они стримят вход, а не строят списки.

Декоратор, выполняющий мемоизацию функции: он кэширует результаты по аргументам вызова и отдаёт сохранённый результат при повторах, вытесняя наименее недавно использованные записи сверх maxsize. Аргументы должны быть хэшируемыми.

Каррирование превращает функцию многих аргументов в цепочку функций одного аргумента, каждая возвращает следующую. Частичное применение — functools.partial(f, a) — фиксирует часть аргументов и возвращает callable для остальных.

Функциональные версии операторов и доступов Python — add, mul, lt, плюс itemgetter, attrgetter, methodcaller. Это более быстрые и picklable замены крошечных лямбд, в основном как key= в sorted/max или в functools.reduce, например sorted(rows, key=itemgetter(1)).

Хвостовая рекурсия — когда рекурсивный вызов является последним действием функции и после его возврата вычислять нечего; обычно достигается параметром-аккумулятором, несущим текущий результат, например fact(n-1, acc*n).

Нет. CPython не выполняет оптимизацию хвостовых вызовов — это намеренный выбор ради полных трейсбеков — поэтому даже хвостово-рекурсивные вызовы растят стек и упираются в лимит рекурсии (по умолчанию ~1000, sys.setrecursionlimit).