Рекурсия, хвостовые вызовы и как не переполнить стек

В предыдущих статьях курса мы отказались от мутации: функции стали чистыми (https://courses.digitable.life/post/functional-programming/01-pure-functions/), данные — неизменяемыми (https://courses.digitable.life/post/functional-programming/02-immutability/). У этого решения есть немедленное и неприятное последствие, о котором обычно молчат в восторженных введениях в ФП.

Посмотрите на обычный цикл:

total = 0                 # мутируемая переменная-аккумулятор
for x in items:           # мутируемый счётчик/итератор
    total += x            # мутация

Здесь три мутации в трёх строках. Цикл for/while — это синтаксис, встроенный в язык специально для того, чтобы менять переменные. Если мутации запрещены, цикл теряет смысл: тело выполнится, ничего не изменит, и следующая итерация будет идентична предыдущей. Бесконечный цикл, который ничего не делает.

Значит, нужен другой механизм повторения. И он один: рекурсия. Не потому, что она красивая, а потому, что это единственный способ выразить «сделай снова, но с другими значениями», не меняя ни одной ячейки памяти. Новая итерация — это новый вызов с новыми аргументами.

Дальше выясняется, что наивная рекурсия падает на 10000 элементах. Эта статья — про то, почему падает и как чинить.

Сначала боль: RecursionError на ровном месте

Простая задача: посчитать сумму списка чисел. Функциональное решение пишется за десять секунд:

def total(xs: list[int]) -> int:
    if not xs:
        return 0
    return xs[0] + total(xs[1:])   # голова + сумма хвоста

Красиво, чисто, ничего не мутирует. Работает на списке из десяти чисел, на сотне, на тысяче. А на списке из 10 000 падает:

RecursionError: maximum recursion depth exceeded

Более того — даже до падения эта функция катастрофически неэффективна: xs[1:] копирует хвост списка на каждом шаге, что даёт O(n²) по времени и O(n²) по памяти для суммирования. Но даже если исправить копирование (передавать индекс), останется главная проблема: O(n) по стеку.

Тот же код на Elixir на списке в миллион элементов отработает без единой жалобы. На Haskell — тоже, хотя и по другой причине и с собственными подводными камнями. На TypeScript в Node.js — упадёт с RangeError: Maximum call stack size exceeded примерно на 11 000.

Чтобы понимать, почему поведение так расходится, надо один раз внимательно посмотреть, что происходит в железе.

Что такое стек вызовов и почему он кончается

Когда функция вызывает функцию, исполнителю нужно где-то хранить контекст паузы: адрес возврата, значения аргументов и локальных переменных, сохранённые регистры. Этот блок называется кадром стека (stack frame), а сами кадры укладываются друг на друга в непрерывной области памяти — стеке.

Ключевой момент: кадр нельзя освободить, пока во внешней функции осталась невыполненная работа после вызова. В нашем total после рекурсивного вызова остаётся сложение xs[0] + .... Значит, все n кадров обязаны дожить до момента, когда самый глубокий вызов вернёт 0, — и только потом n сложений выполнятся в обратном порядке.

Стек — это фиксированный (или медленно растущий) кусок памяти. Реальные лимиты по умолчанию:

Обратите внимание на закономерность: платформы, спроектированные под функциональный стиль (BEAM, GHC), не имеют жёсткого стека фиксированного размера. Это не совпадение — их авторы знали, что рекурсия будет основным механизмом повторения.

Отдельно про Python: начиная с 3.11 вызовы Python-функций из Python-функций инлайнятся интерпретатором и больше не расходуют C-стек, а с 3.12 лимит рекурсии стал заметно ближе к реальной защите от исчерпания памяти, чем раньше. Но sys.setrecursionlimit(10**6) по-прежнему опасен: если в цепочке окажется вызов через C (например, __repr__, sorted с ключом, декоратор на C), вы получите не аккуратный RecursionError, а честный segfault. Подробности — в документации sys.setrecursionlimit.

Рекурсия — это индукция, а не магия

Прежде чем чинить, стоит зафиксировать способ мышления. Рекурсивная функция строится ровно как доказательство по индукции:

1. База. Что вернуть для минимального случая, который дальше не разбирается (пустой список, ноль, лист дерева).
2. Шаг. Как получить ответ для входа размера n, если считать, что для меньшего входа функция уже работает правильно.
3. Убывание. Каждый рекурсивный вызов должен получать вход, строго меньший по некоторой мере, которая не может убывать бесконечно.

Третий пункт — тот самый, который забывают. «Строго меньше по фундированной мере» (well-founded) означает: существует величина, которая на каждом шаге уменьшается и ограничена снизу. Для списка это длина, для числа — значение, для дерева — высота или число узлов.

Главный психологический приём: не разворачивайте рекурсию в голове. Не пытайтесь проследить total([1,2,3]) → 1 + total([2,3]) → 1 + (2 + total([3])). Вместо этого используйте индуктивную гипотезу: «я верю, что total(хвост) вернёт сумму хвоста; тогда мой ответ — голова плюс это». Программисты, которые пытаются симулировать стек мысленно, ломаются на глубине три. Программисты, которые доверяют гипотезе, пишут рекурсию любой сложности.

Когда рекурсия следует за формой данных — она называется структурной (structural recursion), и завершение получается автоматически: список конечен, значит, разбор до пустого списка конечен. Это самый безопасный вид рекурсии, и именно его вы будете писать в 90% случаев. Алгебраические типы данных (https://courses.digitable.life/post/functional-programming/06-adt-and-pattern-matching/) существуют во многом ради того, чтобы структурная рекурсия читалась как определение.

Хвостовой вызов: определение через ту самую боль

Вернёмся к кадру, который «нельзя освободить, пока осталась работа». Инвертируем утверждение: если после вызова работы не осталось, кадр можно освободить прямо перед вызовом.

Вызов g(...) внутри функции f называется хвостовым (tail call), если результат g немедленно становится результатом f — между возвратом g и возвратом f нет ни одной операции. Тогда кадр f бесполезен: возвращаться в него незачем, он только прокинет значение дальше. Компилятор может выкинуть кадр f и заменить вызов на переход (jmp) с новыми аргументами. Это и есть оптимизация хвостовых вызовов (tail call optimization, TCO); частный случай, когда g — это сама f, называют оптимизацией хвостовой рекурсии.

Разница выражается в одной строке кода:

return n + fact(n - 1)   # НЕ хвостовой: после вызова надо умножить... то есть сложить
return fact(n - 1)       # хвостовой: результат отдаётся как есть

Классические ловушки — вызовы, которые выглядят хвостовыми, но не являются:

return f(n - 1) + 0          # сложение после вызова
return -f(n - 1)             # унарный минус после вызова
return list(f(n - 1))        # преобразование после вызова

try:
    return f(n - 1)          # НЕ хвостовой: кадр нужен для обработчика except
except ValueError:
    return 0

with open(path) as fh:
    return f(fh)             # НЕ хвостовой: кадр нужен, чтобы закрыть файл

Последние два случая — важные. Любая конструкция, которая должна выполнить код после возврата (обработчик исключения, finally, освобождение ресурса, деструктор в C++, defer в Go), делает вызов не хвостовым по определению.

Аккумулятор: как превратить рекурсию в хвостовую

Приём один, и он универсален для линейной рекурсии: перенести отложенную работу из «после вызова» в аргумент. Если после вызова мы собирались прибавить n, значит, прибавим его до вызова и передадим внутрь. Такой аргумент называется аккумулятором.

Было (работа копится в стеке):

total([1,2,3]) = 1 + (2 + (3 + 0))

Стало (работа копится в аргументе):

loop([1,2,3], 0) = loop([2,3], 1) = loop([3], 3) = loop([], 6) = 6

Каноническая запись на Haskell — здесь хорошо видно, что публичная функция просто задаёт начальное значение аккумулятора, а вся работа в локальном цикле:

total :: [Int] -> Int
total xs = go xs 0
  where
    go []     acc = acc              -- база: аккумулятор и есть ответ
    go (x:rest) acc = go rest (acc + x)  -- хвостовой вызов: после него ничего нет

Elixir — тот же паттерн, идиома «публичная def + приватная defp с аккумулятором»:

defmodule Sum do
  @spec total([integer()]) :: integer()
  def total(list), do: do_total(list, 0)

  # База: список кончился — возвращаем накопленное
  defp do_total([], acc), do: acc

  # Шаг: сопоставление с образцом разбирает список на голову и хвост.
  # Вызов do_total/2 — последнее выражение тела, значит BEAM переиспользует кадр.
  defp do_total([head | tail], acc), do: do_total(tail, acc + head)
end

Sum.total(Enum.to_list(1..10_000_000))
# => 50000005000000 — миллионы кадров не нужны, стек не растёт

TypeScript и Python — тот же код, но, забегая вперёд, без выигрыша, потому что TCO там нет (об этом ниже):

function total(xs: readonly number[]): number {
  const go = (i: number, acc: number): number =>
    i === xs.length ? acc : go(i + 1, acc + xs[i]);   // хвостовой вызов
  return go(0, 0);
}

def total(xs: list[int]) -> int:
    def go(i: int, acc: int) -> int:
        if i == len(xs):
            return acc
        return go(i + 1, acc + xs[i])     # хвостовой вызов — но CPython его не оптимизирует
    return go(0, 0)

Порядок обхода меняется — следите за этим

Аккумуляторная версия обрабатывает элементы слева направо, а обычная рекурсия сворачивает справа налево. Для сложения это неважно (ассоциативно и коммутативно), а для построения списка — критично:

# Наивная реализация map: НЕ хвостовая, но порядок сохраняется.
defp map_naive([], _f), do: []
defp map_naive([h | t], f), do: [f.(h) | map_naive(t, f)]

# Хвостовая: строим список приписыванием в голову — получаем перевёрнутый результат.
defp map_tail([], _f, acc), do: :lists.reverse(acc)   # разворот в конце: O(n)
defp map_tail([h | t], f, acc), do: map_tail(t, f, [f.(h) | acc])

Приписывание в голову списка — O(1), приписывание в хвост — O(n), поэтому «накопить наоборот и один раз развернуть» даёт O(n), а «дописывать в конец» — O(n²). Это одна из самых частых ошибок производительности у новичков в Elixir и Haskell.

Отдельная эрлангистская тонкость: официальное руководство по эффективности Erlang Efficiency Guide прямо говорит, что «хвостовая рекурсия всегда быстрее» — миф. Для построения списков не-хвостовая map_naive часто быстрее хвостовой с последующим reverse, потому что не делает второй проход и не создаёт мусор. Хвостовая рекурсия обязательна там, где глубина не ограничена (обработка потока, цикл сервера), а не везде подряд.

Когда аккумулятор не помогает

Древовидная рекурсия — обход бинарного дерева, быстрая сортировка, fib — имеет два и более рекурсивных вызова. Хвостовым может быть только последний, первый — принципиально нет. Полностью хвостовой её делают либо переходом к явному стеку, либо CPS (см. ниже).

Хорошая новость: для сбалансированного дерева глубина O(log n), и 1 000 000 узлов — это всего 20 кадров. Не-хвостовая рекурсия по дереву совершенно нормальна. Опасны вырожденные деревья (отсортированный вход в несбалансированный BST превращает дерево в список глубиной n) и обход глубоко вложенных JSON из внешнего источника — классический вектор DoS-атаки.

Где TCO есть, а где нет

Это самая практически важная таблица статьи.

Аргументы против TCO не идеологические, а инженерные, и их стоит знать:

1. Стек-трейс исчезает. Если кадры переиспользованы, трассировка исключения показывает не путь вызовов, а огрызок. Отладка глубокой хвостовой рекурсии — отдельное удовольствие; в Erlang с этим живут, но живут осознанно.
2. Оптимизация невидима и хрупка. Добавили try/finally вокруг вызова — TCO молча отвалилась, программа падает в проде на больших данных. Именно поэтому Scala и Kotlin сделали её явной и проверяемой: @tailrec — это контракт, а не удача.
3. Семантика мешает. Для JVM это ломает механизмы, завязанные на стек вызовов (StackWalker, старые security manager’ы).

Практический вывод для Scala/Kotlin: всегда ставьте @tailrec/tailrec. Компилятор превратит «надеюсь, оптимизировалось» в ошибку компиляции.

tailrec fun total(xs: List<Int>, i: Int = 0, acc: Long = 0): Long =
    if (i == xs.size) acc else total(xs, i + 1, acc + xs[i])
// Уберите tailrec — код скомпилируется и упадёт на большом списке.
// Оставьте tailrec и добавьте "+ 0" после вызова — не скомпилируется. Это и нужно.

Ленивость меняет правила: Haskell — особый случай

В Haskell «хвостовая рекурсия» — не синоним «без переполнения», и это ловит всех новичков.

-- Хвостовая по форме. И тем не менее взрывается на больших списках.
sumLazy :: [Int] -> Int
sumLazy = go 0
  where go acc []     = acc
        go acc (x:xs) = go (acc + x) xs

Из-за ленивости acc + x не вычисляется, а превращается в thunk — отложенное вычисление. К концу списка acc — это цепочка из миллиона thunk’ов ((((0+1)+2)+3)+...), лежащая в куче. Когда её наконец форсируют, вычисление разворачивается — и переполняет стек. Формально стек не рос во время рекурсии; он вырос при вычислении результата.

Лечение — форсировать аккумулятор на каждом шаге:

{-# LANGUAGE BangPatterns #-}

sumStrict :: [Int] -> Int
sumStrict = go 0
  where go !acc []     = acc          -- ! требует WHNF-вычисления acc до вызова
        go !acc (x:xs) = go (acc + x) xs

-- То же самое стандартными средствами:
-- foldl  — ленивый аккумулятор, space leak
-- foldl' — строгий аккумулятор, правильный выбор (Data.List)
sumBest :: [Int] -> Int
sumBest = foldl' (+) 0

Зеркальный сюрприз: в Haskell не-хвостовая рекурсия часто работает на бесконечных данных, а хвостовая — нет.

-- Guarded recursion (corecursion): рекурсивный вызов спрятан под конструктором (:).
-- Вызов не выполняется, пока потребитель не запросит следующий элемент.
myMap :: (a -> b) -> [a] -> [b]
myMap _ []     = []
myMap f (x:xs) = f x : myMap f xs

take 5 (myMap (*2) [1..])   -- [2,4,6,8,10] на бесконечном списке

Хвостовая версия myMap с аккумулятором на бесконечном списке зависнет навсегда: она обязана дойти до конца, а конца нет. Это подводит к теме ленивости и потоков (https://courses.digitable.life/post/functional-programming/11-laziness-and-streams/), где такое поведение — не баг, а основной инструмент.

Мораль: правило «делай хвостовую рекурсию» — не универсальный закон, а рекомендация для строгих языков. В ленивом языке нужно думать не о кадрах, а о том, где именно наступает вычисление.

Как жить без TCO: четыре рабочих техники

1. Развернуть в цикл руками

Хвостовая рекурсия изоморфна циклу while: аргументы функции становятся переменными цикла, хвостовой вызов — присваиванием и переходом на начало. Это ровно то, что делает компилятор с TCO; в языке без TCO это делаете вы.

def total(xs: list[int]) -> int:
    i, acc = 0, 0            # аргументы стали переменными
    while i != len(xs):      # база стала условием выхода
        i, acc = i + 1, acc + xs[i]   # хвостовой вызов стал присваиванием
    return acc
# Время O(n), память O(1). В Python это не «предательство ФП», а трезвость.

Важно: цикл здесь мутирует локальные переменные, невидимые снаружи. Функция остаётся чистой — референциальная прозрачность не нарушена. Это законный приём «функциональное снаружи, императивное внутри», и он лежит в основе архитектурного паттерна functional core / imperative shell (https://courses.digitable.life/post/functional-programming/16-architecture-and-practice/).

2. Трамплин

Что делать, если самовызова нет — например, при взаимной рекурсии? Классика:

def is_even(n): return True  if n == 0 else is_odd(n - 1)
def is_odd(n):  return False if n == 0 else is_even(n - 1)

is_even(100_000)   # RecursionError

Идея трамплина: функция не вызывает следующий шаг, а возвращает описание следующего шага. Внешний цикл — «батут» — принимает описание и выполняет его. Стек никогда не растёт, потому что каждый шаг возвращается наружу.

from typing import Callable, Union
from dataclasses import dataclass

@dataclass(frozen=True)
class Bounce:
    """Отложенный шаг: вместо вызова возвращаем функцию, которую надо вызвать."""
    thunk: Callable[[], "Bounce | object"]

def trampoline(result):
    # Пока нам возвращают Bounce — раскручиваем. Один кадр стека на всё.
    while isinstance(result, Bounce):
        result = result.thunk()
    return result

def is_even(n: int):
    return True if n == 0 else Bounce(lambda: is_odd(n - 1))

def is_odd(n: int):
    return False if n == 0 else Bounce(lambda: is_even(n - 1))

trampoline(is_even(1_000_000))   # True, стек не растёт

Тот же приём на TypeScript, где он особенно востребован (в V8 TCO нет):

type Thunk<T> = { done: false; next: () => Thunk<T> } | { done: true; value: T };

const more = <T>(next: () => Thunk<T>): Thunk<T> => ({ done: false, next });
const done = <T>(value: T): Thunk<T> => ({ done: true, value });

function trampoline<T>(start: Thunk<T>): T {
  let cur = start;
  while (!cur.done) cur = cur.next();   // единственный кадр
  return cur.value;
}

const sumTo = (n: number, acc = 0): Thunk<number> =>
  n === 0 ? done(acc) : more(() => sumTo(n - 1, acc + n));

trampoline(sumTo(10_000_000));  // 50000005000000

Цена трамплина честная и заметная: на каждый шаг создаётся объект-замыкание. Это выделение в куче, работа для GC и потеря инлайнинга. По моим замерам и общей практике замедление относительно голого цикла — в 3–10 раз, зависит от рантайма. Трамплин применяют там, где важна форма кода (интерпретаторы, парсеры, state-машины, библиотеки эффектов), а не в горячем цикле обработки миллиона чисел.

В Clojure трамплин встроен в язык — clojure.core/trampoline. Это прямое признание того, что JVM не даёт TCO.

3. Явный стек в куче

Для древовидной рекурсии самый прямой путь — вынести стек из системного в обычный список/массив в куче. Куча растёт до объёма памяти, а не до мегабайта.

def tree_sum(root) -> int:
    """Обход дерева без рекурсии. Время O(n), память O(h) в куче, h — высота."""
    total, stack = 0, [root]
    while stack:
        node = stack.pop()
        if node is None:
            continue
        total += node.value
        stack.append(node.left)      # порядок обхода задаём сами
        stack.append(node.right)
    return total

Плюс к устойчивости: явный стек позволяет приостанавливать и возобновлять обход, сохранять его состояние, ограничивать глубину (защита от вредоносного JSON). Минус — код перестаёт читаться как определение задачи. Это ровно тот trade-off, о котором стоит говорить честно: вы обменяли декларативность на контроль.

Родственный приём — генераторы: они дают ленивый обход с O(h) памяти в куче, но вложенные yield from всё ещё расходуют стек интерпретатора, так что глубину это не спасает автоматически.

4. Мемоизация: когда проблема не в глубине, а в ширине

Отдельный класс бед — древовидная рекурсия с перекрывающимися подзадачами:

Глубина всего 5, стек в порядке — но одинаковые узлы (окрашенные) считаются заново. Наивный fib(n) делает O(φⁿ) ≈ O(1.618ⁿ) вызовов: fib(50) — это порядка 2,7 млрд вызовов, минуты работы.

Спасение — то самое свойство чистых функций, ради которого мы городили огород: чистую функцию можно кешировать, потому что она всегда даёт один ответ на один вход.

from functools import cache

@cache                       # стандартная мемоизация из functools
def fib(n: int) -> int:
    return n if n < 2 else fib(n - 1) + fib(n - 2)

fib(300)                     # мгновенно: O(n) времени, O(n) памяти

# В Elixir нет мутируемого кеша, поэтому аккумулятор несёт пару соседних чисел.
# Время O(n), память O(1) кадров — хвостовая рекурсия.
def fib(n), do: do_fib(n, 0, 1)
defp do_fib(0, a, _b), do: a
defp do_fib(n, a, b), do: do_fib(n - 1, b, a + b)

Сводка по трём подходам к fib:

Подробный разбор динамического программирования — в треке алгоритмов (https://courses.digitable.life/post/algorithms/00-overview/); здесь важно запомнить связь: мемоизация возможна ровно потому, что функция чистая.

Цена рекурсии: честный разговор

Курс обещал не продавать ФП, а показывать цену. Вот она.

Производительность. Даже с TCO хвостовая рекурсия обычно чуть медленнее цикла: вызов — это как минимум передача аргументов, а компиляторы JIT агрессивнее оптимизируют классические циклы (развёртка, векторизация, вынос инвариантов). Не-хвостовая рекурсия дороже заметно: каждый кадр — это запись в память и промах кеша при возврате. Разрыв между for-циклом на массиве и рекурсией по связному списку легко достигает порядка величины — и дело не в вызовах, а в локальности данных: массив читается последовательно, список прыгает по куче.

Кривая обучения. Рекурсию «понимают» на третий-четвёртый раз. Переписывание рекурсии в хвостовую форму — отдельный навык: надо увидеть отложенную операцию и научиться её накапливать, а для некоммутативных операций ещё и не перепутать порядок. CPS-преобразование — навык более высокого уровня, и код после него читает мало кто.

Отладка. С TCO вы теряете стек-трейс. Без TCO вы получаете стек-трейс на тысячу одинаковых строк, в котором ничего не видно. Профилировщики плохо показывают рекурсивные горячие точки: время «размазано» по одной функции.

Где рекурсия прямо мешает. Плоский проход по массиву чисел, любой численный код, обработка байтовых буферов, горячие циклы рендеринга — всё это на рекурсии пишется хуже по всем измерениям. Здесь for не «императивная слабость», а правильный инструмент.

Где рекурсия однозначно выигрывает. Всё, что рекурсивно по природе: деревья (AST, DOM, файловая система, JSON), парсеры, интерпретаторы, поиск с возвратом (backtracking), разделяй-и-властвуй, обход графов. Здесь итеративная версия с ручным стеком — это та же рекурсия, только написанная хуже.

Разумная позиция: писать по форме данных. Данные рекурсивны — пишем рекурсию. Данные плоские — пишем цикл или, ещё лучше, map/filter/reduce, которые скрывают повторение целиком.

Свёртки: рекурсия, которую написали за вас

Финальное наблюдение статьи. Почти вся линейная рекурсия по списку — это одна из двух схем:

-- Правая свёртка: не-хвостовая, дружит с ленивостью и бесконечными списками
foldr f z [x1, x2, x3] = f x1 (f x2 (f x3 z))

-- Левая свёртка: хвостовая, работает с аккумулятором
foldl f z [x1, x2, x3] = f (f (f z x1) x2) x3

sum, product, length, map, filter, reverse, concat — всё это частные случаи. Поэтому в реальном функциональном коде явная рекурсия встречается редко: её пишут один раз внутри библиотечной свёртки, а прикладной код вызывает Enum.reduce, foldl', reduce, array.reduce.

# Идиоматичный Elixir: явной рекурсии нет, но внутри Enum.reduce она есть
1..10_000_000
|> Enum.reduce(0, &+/2)

Это общий принцип ФП, который будет повторяться весь курс: рекурсию заменяют комбинатором. Сначала мы упаковали повторение в fold, дальше упакуем композицию функций (https://courses.digitable.life/post/functional-programming/05-composition-and-currying/), потом — обработку контейнеров в функторы (https://courses.digitable.life/post/functional-programming/07-functors-and-applicatives/) и последовательность эффектов в монады (https://courses.digitable.life/post/functional-programming/08-monads/). Каждый раз — один и тот же ход: заметили повторяющуюся схему, дали ей имя, перестали писать руками.

Обобщение свёрток на произвольные рекурсивные типы называется катаморфизмом; к нему мы вернёмся в карте абстракций (https://courses.digitable.life/post/functional-programming/09-functor-map/).

Чек-лист: типичные ошибки

1. Нет базового случая или он недостижим. if n == 0 при уменьшении на 2 из нечётного n — бесконечная рекурсия.
2. Шаг не уменьшает меру. f(xs) вместо f(tail) — компилируется, зависает.
3. xs[1:] в Python / slice в JS. Копирование хвоста превращает O(n) в O(n²). Передавайте индекс.
4. Дописывание в конец списка. acc ++ [x] в Haskell/Elixir — O(n) на шаг, O(n²) итого. Копите в голову и разворачивайте один раз.
5. Вера в TCO там, где его нет. Python, Java, C#, Node.js — TCO нет. Хвостовая форма не спасёт.
6. try/with/finally вокруг хвостового вызова — TCO молча отключается.
7. Ленивый аккумулятор в Haskell. foldl вместо foldl', отсутствие ! — space leak вместо экономии.
8. sys.setrecursionlimit(10**6) как «решение». Вы не убрали проблему, а поменяли RecursionError на segfault.
9. Рекурсия по данным из внешнего мира без ограничения глубины. Вложенный на 100 000 уровней JSON — готовый DoS. Ограничивайте глубину явно.
10. Забытый @tailrec в Scala / tailrec в Kotlin. Аннотация бесплатна и превращает надежду в проверку компилятора.

Итог

• Отказ от мутации убирает циклы, поэтому рекурсия в ФП — не украшение, а базовый механизм повторения.
• Кадр стека нельзя освободить, пока после вызова осталась работа. Отсюда O(n) стека и переполнение.
• Хвостовой вызов — вызов, результат которого сразу становится результатом функции. Кадр можно переиспользовать; TCO превращает рекурсию в переход, память падает до O(1).
• Универсальный приём — аккумулятор: перенести отложенную работу из стека в аргумент. Помните про смену порядка обхода.
• TCO есть в Scheme, Erlang/Elixir, Haskell, OCaml, F#; ограниченно — в Scala и Kotlin; нет в Python, Java, C#, Node.js.
• Без TCO работают: ручной цикл (для самовызова), трамплин (для взаимной рекурсии, ценой аллокаций), явный стек в куче и мемоизация (когда проблема в перекрывающихся подзадачах, а не в глубине).
• В ленивом Haskell «хвостовая» не значит «безопасная»: следите за строгостью аккумулятора (foldl', BangPatterns) и цените охраняемую рекурсию на бесконечных структурах.
• В прикладном коде явная рекурсия нужна редко — её вытесняют свёртки и комбинаторы.

Что почитать

• Harold Abelson, Gerald Jay Sussman. Structure and Interpretation of Computer Programs — раздел 1.2 про рекурсивные и итеративные процессы: до сих пор лучшее объяснение разницы.
• Erlang Efficiency Guide: List handling / Myths — почему «хвостовая рекурсия всегда быстрее» неправда.
• HaskellWiki: Stack overflow и Foldr Foldl Foldl’ — разбор ленивых аккумуляторов.
• Guido van Rossum. Tail Recursion Elimination — аргументация против TCO в Python.
• ECMAScript: Tail Position Calls и таблица поддержки — почему в спеке есть, а в V8 нет.
• Kent Dybvig. The Scheme Programming Language, глава про proper tail calls.

Что дальше

Мы научились повторять вычисление, не мутируя ничего. Следующий шаг — научиться соединять функции друг с другом так, чтобы программа читалась как конвейер преобразований, а не как набор вложенных вызовов: Композиция, каррирование, частичное применение и конвейеры.