У меня есть следующий кусок кода, который завершается с ошибкой:

RuntimeError: превышена максимальная глубина рекурсии

Я попытался переписать это, чтобы учесть оптимизацию хвостовой рекурсии (TCO). Я считаю, что этот код должен был быть успешным, если бы имелась ТШО.

def trisum(n, csum):
    if n == 0:
        return csum
    else:
        return trisum(n - 1, csum + n)

print(trisum(1000, 0))

Должен ли я заключить, что Python не выполняет никаких типов TCO, или мне просто нужно определить его по-другому?

Нет, и никогда не будет, так как Гвидо ван Россум предпочитает иметь надлежащие трассировки:

Исключение рекурсии хвоста (2009-04-22)

Заключительные слова о вызовах в хвост (2009-04-27)

Вы можете вручную исключить рекурсию с помощью преобразования, подобного этому:

>>> def trisum(n, csum):
...     while True:                     # Change recursion to a while loop
...         if n == 0:
...             return csum
...         n, csum = n - 1, csum + n   # Update parameters instead of tail recursion

>>> trisum(1000,0)
500500

Я опубликовал модуль, выполняющий оптимизацию хвостового вызова (обрабатывая как хвостовую рекурсию, так и стиль продолжения продолжения): https://github.com/baruchel/tco

Оптимизация хвостовой рекурсии в Python

Часто утверждается, что хвостовая рекурсия не подходит к пиктоническому способу кодирования, и что не нужно заботиться о том, как встроить ее в цикл. Я не хочу спорить с этой точкой зрения; однако иногда мне нравится пробовать или реализовывать новые идеи в виде хвостовых рекурсивных функций, а не с помощью циклов по разным причинам (фокусируясь на идее, а не на процессе, имея на экране двадцать коротких функций одновременно, а не только три «Pythonic») функции, работающие в интерактивном сеансе вместо редактирования моего кода и т. д.).

Оптимизация хвостовой рекурсии в Python на самом деле довольно проста. Хотя говорят, что это невозможно или очень сложно, я думаю, что этого можно достичь с помощью элегантных, коротких и общих решений; Я даже думаю, что большинство из этих решений не используют функции Python иначе, чем должны. Чистые лямбда-выражения, работающие вместе со стандартными циклами, приводят к быстрым, эффективным и полностью используемым инструментам для реализации оптимизации хвостовой рекурсии.

Для личного удобства я написал небольшой модуль, реализующий такую ​​оптимизацию двумя различными способами. Я хотел бы обсудить здесь две мои основные функции.

Чистый путь: модификация Y комбинатора

Y комбинатор хорошо известен; он позволяет рекурсивно использовать лямбда-функции, но сам по себе не позволяет встраивать рекурсивные вызовы в цикл. Лямбда-исчисление само по себе не может сделать такую ​​вещь. Небольшое изменение в Y-комбинаторе, однако, может защитить рекурсивный вызов для фактической оценки. Таким образом, оценка может быть отложена.

Вот знаменитое выражение для Y комбинатора:

lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(*args)))

С очень небольшим изменением я мог получить:

lambda f: (lambda x: x(x))(lambda y: f(lambda *args: lambda: y(y)(*args)))

Вместо того, чтобы вызывать себя, функция f теперь возвращает функцию, выполняющую тот же самый вызов, но, поскольку она ее возвращает, оценку можно выполнить позже извне.

Мой код:

def bet(func):
    b = (lambda f: (lambda x: x(x))(lambda y:
          f(lambda *args: lambda: y(y)(*args))))(func)
    def wrapper(*args):
        out = b(*args)
        while callable(out):
            out = out()
        return out
    return wrapper

Функцию можно использовать следующим образом; Вот два примера с хвостовой рекурсивной версией факториала и Фибоначчи:

>>> from recursion import *
>>> fac = bet( lambda f: lambda n, a: a if not n else f(n-1,a*n) )
>>> fac(5,1)
120
>>> fibo = bet( lambda f: lambda n,p,q: p if not n else f(n-1,q,p+q) )
>>> fibo(10,0,1)
55

Очевидно, глубина рекурсии больше не является проблемой:

>>> bet( lambda f: lambda n: 42 if not n else f(n-1) )(50000)
42

Это, конечно, единственная реальная цель функции.

С этой оптимизацией нельзя сделать только одно: ее нельзя использовать с хвостовой рекурсивной функцией, выполняющей оценку другой функции (это связано с тем фактом, что все возвращаемые объекты с возможностью вызова обрабатываются как дальнейшие рекурсивные вызовы без различия). Поскольку мне обычно не нужна такая функция, я очень доволен приведенным выше кодом. Однако, чтобы предоставить более общий модуль, я подумал немного больше, чтобы найти обходной путь для этой проблемы (см. Следующий раздел).

Что касается скорости этого процесса (который, однако, не является реальной проблемой), то он довольно хорош; хвостовые рекурсивные функции даже оцениваются гораздо быстрее, чем в следующем коде с использованием более простых выражений:

def bet1(func):
    def wrapper(*args):
        out = func(lambda *x: lambda: x)(*args)
        while callable(out):
            out = func(lambda *x: lambda: x)(*out())
        return out
    return wrapper

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

Продолжение прохождения стиля с исключениями

Вот более общая функция; он способен обрабатывать все хвостовые рекурсивные функции, включая те, которые возвращают другие функции. Рекурсивные вызовы распознаются из других возвращаемых значений с помощью исключений. Это решение медленнее, чем предыдущее; более быстрый код, вероятно, можно было бы написать, используя некоторые специальные значения, поскольку «флаги» обнаруживаются в основном цикле, но мне не нравится идея использования специальных значений или внутренних ключевых слов. Существует некоторая забавная интерпретация использования исключений: если Python не любит хвост-рекурсивные вызовы, то должно возникать исключение, когда происходит хвост-рекурсивный вызов, и Pythonic будет перехватывать исключение, чтобы найти некоторый чистый решение, которое на самом деле то, что происходит здесь ...

class _RecursiveCall(Exception):
  def __init__(self, *args):
    self.args = args
def _recursiveCallback(*args):
  raise _RecursiveCall(*args)
def bet0(func):
    def wrapper(*args):
        while True:
          try:
            return func(_recursiveCallback)(*args)
          except _RecursiveCall as e:
            args = e.args
    return wrapper

Теперь все функции могут быть использованы. В следующем примере f(n)оценивается функция тождества для любого положительного значения n:

>>> f = bet0( lambda f: lambda n: (lambda x: x) if not n else f(n-1) )
>>> f(5)(42)
42

Конечно, можно утверждать, что исключения не предназначены для преднамеренного перенаправления интерпретатора (как своего рода gotoутверждение или, скорее, скорее как стиль передачи продолжения), что я должен признать. Но, опять же, я нахожу забавной идею использования tryодной строки, являющейсяreturn оператором: мы пытаемся что-то вернуть (нормальное поведение), но мы не можем этого сделать из-за рекурсивного вызова (исключение).

Первоначальный ответ (2013-08-29).

Я написал очень маленький плагин для обработки хвостовой рекурсии. Вы можете найти это с моими объяснениями там: https://groups.google.com/forum/?hl=fr#!topic/comp.lang.python/dIsnJ2BoBKs

Он может встроить лямбда-функцию, написанную в стиле хвостовой рекурсии, в другую функцию, которая будет оценивать ее как цикл.

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

Слово Гвидо находится по адресу http://neopythonic.blogspot.co.uk/2009/04/tail-recursion-elmination.html

Недавно я опубликовал в своем блоге Python History статью о происхождении функциональных возможностей Python. Дополнительное замечание о том, что не поддерживается удаление хвостовой рекурсии (TRE), сразу вызвало несколько комментариев о том, как жаль, что Python этого не делает, включая ссылки на последние записи в блоге других, пытающихся «доказать», что TRE может быть добавлено в Python. без труда. Итак, позвольте мне защитить свою позицию (то есть, я не хочу, чтобы TRE на языке). Если вам нужен короткий ответ, он просто не пифоничен. Вот длинный ответ:

CPython не поддерживает и, вероятно, никогда не будет поддерживать оптимизацию хвостовых вызовов на основе Гвидо ван Россума высказываний по этому вопросу.

Я слышал аргументы, что это затрудняет отладку из-за того, как он изменяет трассировку стека.

Попробуйте экспериментальную реализацию TCO для определения размера.

Помимо оптимизации хвостовой рекурсии, вы можете установить глубину рекурсии вручную:

import sys
sys.setrecursionlimit(5500000)
print("recursion limit:%d " % (sys.getrecursionlimit()))