Пример (факториал) и обсуждение.
Математически: $n!=n\cdot (n-1)!$. Хвостовая форма переписывает рекурренту как
$$f(n,acc)=\{\begin{array}{ll}acc,& n=0\\ f(n-1,n\cdot acc),& n>0\end{array}$$ (т.е. аккумулируем результат в параметре $acc$).
Пример в Python:
```python
# Обычная (не-хвостовая) рекурсия — при больших n переполнит стек
def fact(n):
if n == 0:
return 1
return n * fact(n-1)
# Хвостовая рекурсия (логически хвостовая), но CPython не делает TCO
def fact_tr(n, acc=1):
if n == 0:
return acc
return fact_tr(n-1, n * acc)
```
Почему проблема: CPython не выполняет оптимизацию хвостовой рекурсии (TCO), поэтому даже хвостовая версия вызовет переполнение стека при больших $n$.
Способы избежать переполнения стека в интерпретируемых языках без TCO:
1. Переписать в итеративную форму (предпочтительно по простоте и производительности):
```python
def fact_iter(n):
acc = 1
while n > 0:
acc *= n
n -= 1
return acc
```
2. Явный стек (эмуляция рекурсии) — полезно при обходах дерева/графа:
```python
def dfs_iter(root):
stack = [root]
while stack:
node = stack.pop()
# обработка node
for child in node.children:
stack.append(child)
```
3. Трамплин (trampoline) — превращает рекурсивные шаги в отложенные вызовы и выполняет их в цикле:
```python
def trampoline(f, *args, **kwargs):
res = f(*args, **kwargs)
while callable(res):
res = res()
return res
def fact_tr_step(n, acc=1):
if n == 0:
return acc
return lambda: fact_tr_step(n-1, n*acc)
# Использование:
# result = trampoline(fact_tr_step, big_n)
```
Трамплин сохраняет стиль «рекурсивной» записи, но выполняет итеративно, поэтому не растёт стек.
4. CPS (Continuation-Passing Style) или явная трансформация в конечный автомат — сложнее, но даёт контроль над стеком; часто реализуется вместе с трамплином.
5. Увеличить предел рекурсии через sys.setrecursionlimit(n) — краткосрочное решение; опасно (может привести к краху интерпретатора при переполнении C-стека).
6. Использовать реализацию/интерпретатор, поддерживающий TCO (если доступен), либо Stackless/микро-питон/расширение на C — практическое решение для некоторых задач.
7. Перенести тяжёлые рекурсивные вычисления в нативный код (модуль на C/C++) или использовать готовые оптимизированные библиотеки (например, math.factorial).
Вывод: для интерпретаторов без TCO лучше переписывать рекурсию в итеративную форму или использовать трамплин/явный стек; увеличение лимита рекурсии и переход на иные реализации — вспомогательные варианты с оговорками.