Что такое tail recursion

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

Сравните:

# НЕ хвостовая: после рекурсии мы ещё умножаем на n
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)   # после возврата нужно умножить

# Хвостовая: рекурсивный вызов — последний шаг
def factorial_tail(n, acc=1):
    if n == 0:
        return acc
    return factorial_tail(n - 1, acc * n)   # ничего после

В первой версии текущий frame обязан дождаться возврата вложенного, чтобы умножить на n. Поэтому frame нельзя удалить со стека — он хранит n и операцию *.

Во второй версии текущий frame ничего не делает после рекурсивного вызова. Он просто возвращает результат вложенного. С точки зрения вычислений, текущий frame не нужен — его можно удалить ДО создания нового.

Tail Call Optimization (TCO)

Языки с tail call optimization превращают tail-рекурсию в эффективный цикл. Технически: при tail call компилятор перезаписывает текущий frame с новыми аргументами и делает jump в начало функции, вместо настоящего вызова. Глубина рекурсии остаётся константной, не растёт.

С TCO такой код:

(define (factorial n acc)
  (if (= n 0)
      acc
      (factorial (- n 1) (* acc n))))   ; tail call

(factorial 1000000 1)   ; работает без stack overflow

эквивалентен по производительности и памяти такому циклу:

def factorial_iter(n):
    acc = 1
    while n > 0:
        acc = acc * n
        n = n - 1
    return acc

В Scheme, Scala (с @tailrec), Haskell, OCaml, Erlang TCO — встроенная фича. Рекурсия на миллион уровней работает.

Почему в Python нет TCO

Гвидо ван Россум, создатель Python, публично объяснял отсутствие TCO умышленным дизайном:

Причина 1: traceback. Когда программа падает, Python показывает цепочку вызовов:

Traceback (most recent call last):
  File "x.py", line 10, in main
    factorial(5)
  File "x.py", line 5, in factorial
    factorial(4)
  File "x.py", line 5, in factorial
    factorial(3)
  ...

С TCO большинство этих кадров не существовало бы. Вы бы видели только последний — без понимания, через какие вызовы туда пришли. Для debug это потеря.

Причина 2: интроспекция. В Python можно во время выполнения смотреть на sys._getframe(), на цепочку f_back. С TCO эта цепочка ломается.

Причина 3: культура языка. Python предпочитает явный цикл там, где другие языки используют tail рекурсию. Это не баг, это philosophy: «Explicit is better than implicit».

Поэтому даже хвостовая рекурсия в Python создаёт новый frame, накапливает стек и упирается в лимит. Tail recursion в Python не даёт никаких преимуществ перед нехвостовой — и обе они хуже цикла.

Как переписать tail recursion в цикл

Любую хвостовую рекурсию можно механически превратить в while или for. Общий шаблон:

# было: tail recursion
def f_tail(state):
    if base_condition(state):
        return state
    return f_tail(next_state(state))

# стало: цикл
def f_iter(state):
    while not base_condition(state):
        state = next_state(state)
    return state

«State» — это все аргументы функции, объединённые. Например, для factorial:

# tail recursion
def factorial_tail(n, acc=1):
    if n == 0:
        return acc
    return factorial_tail(n - 1, acc * n)

# превращается в
def factorial_iter(n):
    acc = 1
    while n != 0:
        acc = acc * n
        n = n - 1
    return acc

Полностью эквивалентно. Глубина стека O(1). Скорость — на 30% быстрее (нет overhead на вызов).

Не хвостовая рекурсия — сложнее

Если рекурсия не хвостовая (return n * factorial(n-1)), её нельзя превратить в простой цикл напрямую — нужна другая структура. Например, для не-хвостового factorial:

# не хвостовая
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

# превращается в цикл с явным аккумулятором
def factorial_iter(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

Это требует переосмысления алгоритма. Иногда достаточно просто перебрать цикл в правильном направлении. Иногда — нужен явный стек.

Полное преобразование — это:

1. Заменить рекурсию на цикл с явным стеком (list).
2. На каждой итерации pop состояние из стека.
3. Обработать, push новые состояния, если есть.

Этот приём пригодится в следующем уроке, когда будем разбирать обход глубоких структур без рекурсии.

Python 3.13 и tail calls в C-API

В Python 3.13 (релиз 2024) сделан интересный шаг: некоторые встроенные функции на C-уровне используют tail calls в bytecode interpreter. Это даёт ~10-15% ускорения для tight циклов.

Важно: это не TCO для пользовательских Python-функций. Ваши def factorial(n): ... всё равно создают frames при каждом вызове. Изменилось только то, как C-код интерпретатора обрабатывает свои внутренние переходы — пользовательский код это не видит.

Гвидо подтвердил: TCO для Python-функций не появится. Если нужна рекурсия без глубины — пишите цикл явно.

Когда оставлять рекурсию

Рекурсия не виновата сама по себе. Она удобна для:

1. Естественно рекурсивных структур — деревья, графы. Здесь глубина обычно log(n), и читаемость кода важнее микро-производительности.
2. Маленькие глубины — до 100 уровней рекурсия безопасна и читается лучше.
3. Алгоритмы divide-and-conquer — глубина log(n), естественная структура.

Когда переписывать в цикл:

1. Глубина O(n) — линейный спуск.
2. Подозрение на большие входы (миллион элементов).
3. Performance-критичный код (рекурсия в Python дороже цикла).

Замеры

Сравним хвостовой factorial с рекурсивной и итеративной формой:

import timeit
import sys

sys.setrecursionlimit(2000)

def fact_naive(n):
    if n == 0:
        return 1
    return n * fact_naive(n - 1)

def fact_tail(n, acc=1):
    if n == 0:
        return acc
    return fact_tail(n - 1, acc * n)

def fact_iter(n):
    acc = 1
    for i in range(1, n + 1):
        acc *= i
    return acc

n = 800
print(f"naive: {timeit.timeit(lambda: fact_naive(n), number=100):.4f} s")
print(f"tail:  {timeit.timeit(lambda: fact_tail(n), number=100):.4f} s")
print(f"iter:  {timeit.timeit(lambda: fact_iter(n), number=100):.4f} s")

Типичные числа: naive ~0.02 c, tail ~0.025 c (медленнее из-за лишнего аргумента), iter ~0.012 c — в два раза быстрее. В Python tail recursion проигрывает обычной — и обе проигрывают циклу.

Попробуй сам

Переведите этот рекурсивный код в итеративную форму:

# рекурсивный sum_list
def sum_list_rec(xs, i=0, acc=0):
    if i == len(xs):
        return acc
    return sum_list_rec(xs, i + 1, acc + xs[i])

# ваша задача — итеративная версия
def sum_list_iter(xs):
    # ...
    pass

# проверка
xs = list(range(100))
assert sum_list_rec(xs) == sum_list_iter(xs)
assert sum_list_iter(list(range(100_000))) == sum(range(100_000))

Подсказка: state = (i, acc), цикл while i < len(xs). После переписывания итеративная версия работает на любой длине списка, рекурсивная падает на 1000.