Eu tenho o seguinte pedaço de código que falha com o seguinte erro:

RuntimeError: profundidade máxima de recursão excedida

Tentei reescrever isso para permitir a otimização da recursão de cauda (TCO). Acredito que esse código teria sido bem-sucedido se um TCO tivesse ocorrido.

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

print(trisum(1000, 0))

Devo concluir que o Python não faz nenhum tipo de TCO ou preciso apenas defini-lo de maneira diferente?

Não, e nunca será, uma vez que Guido van Rossum prefere ter um rastreio adequado:

Eliminação da recursão da cauda (22-04-2009)

Palavras finais sobre chamadas de cauda (27-04-2009)

Você pode eliminar manualmente a recursão com uma transformação como esta:

>>> 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

Publiquei um módulo executando otimização de chamada de cauda (manipulando o estilo de recursão de cauda e de passagem de continuação): https://github.com/baruchel/tco

Otimizando a recursão da cauda em Python

Afirma-se frequentemente que a recursão da cauda não se adequa à maneira Python de codificar e que não se deve preocupar em incorporá-la em um loop. Não quero discutir com esse ponto de vista; às vezes, no entanto, gosto de tentar ou implementar novas idéias como funções recursivas de cauda em vez de com loops por várias razões (focando na ideia e não no processo, tendo vinte funções curtas na tela ao mesmo tempo, em vez de apenas três "Pythonic" funções, trabalhando em uma sessão interativa em vez de editar meu código etc.).

Otimizar a recursão da cauda no Python é de fato bastante fácil. Embora se diga que é impossível ou muito complicado, acho que pode ser alcançado com soluções elegantes, curtas e gerais; Até acho que a maioria dessas soluções não usa os recursos do Python, do contrário. Expressões lambda limpas, trabalhando com loops muito padrão, levam a ferramentas rápidas, eficientes e totalmente utilizáveis ​​para implementar a otimização da recursão da cauda.

Como conveniência pessoal, escrevi um pequeno módulo implementando essa otimização de duas maneiras diferentes. Eu gostaria de discutir aqui sobre minhas duas funções principais.

A maneira limpa: modificando o combinador Y

O combinador Y é bem conhecido; permite usar funções lambda de maneira recursiva, mas não permite por si só incorporar chamadas recursivas em um loop. O cálculo lambda sozinho não pode fazer uma coisa dessas. Uma ligeira alteração no combinador Y, no entanto, pode proteger a chamada recursiva a ser realmente avaliada. A avaliação pode, portanto, ser adiada.

Aqui está a famosa expressão do combinador Y:

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

Com uma pequena mudança, eu pude obter:

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

Em vez de chamar a si mesma, a função f agora retorna uma função que executa a mesma chamada, mas, como ela retorna, a avaliação pode ser feita posteriormente de fora.

Meu código é:

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

A função pode ser usada da seguinte maneira; Aqui estão dois exemplos com versões recursivas de fatorial e Fibonacci:

>>> 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

Obviamente, a profundidade da recursão não é mais um problema:

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

É claro que esse é o único objetivo real da função.

Somente uma coisa não pode ser feita com essa otimização: ela não pode ser usada com uma função recursiva de cauda avaliando para outra função (isso vem do fato de que objetos retornáveis ​​que podem ser chamados são todos manipulados como chamadas recursivas adicionais sem distinção). Como geralmente não preciso desse recurso, estou muito feliz com o código acima. No entanto, para fornecer um módulo mais geral, pensei um pouco mais para encontrar alguma solução alternativa para esse problema (consulte a próxima seção).

No que diz respeito à velocidade desse processo (que não é o problema real), ele é bastante bom; funções recursivas de cauda são avaliadas até mais rapidamente do que com o código a seguir, usando expressões mais simples:

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

Penso que avaliar uma expressão, mesmo complicada, é muito mais rápida do que avaliar várias expressões simples, como é o caso nesta segunda versão. Eu não mantive essa nova função no meu módulo e não vejo circunstâncias em que ela possa ser usada, e não a "oficial".

Estilo de passagem de continuação com exceções

Aqui está uma função mais geral; é capaz de lidar com todas as funções recursivas da cauda, ​​incluindo aquelas que retornam outras funções. Chamadas recursivas são reconhecidas de outros valores de retorno pelo uso de exceções. Esta solução é mais lenta que a anterior; um código mais rápido provavelmente poderia ser escrito usando alguns valores especiais como "sinalizadores" sendo detectados no loop principal, mas não gosto da idéia de usar valores especiais ou palavras-chave internas. Há alguma interpretação engraçada do uso de exceções: se o Python não gostar de chamadas recursivas de cauda, ​​uma exceção deve ser levantada quando uma chamada recursiva de cauda ocorrer, e a maneira Pythonic será capturar a exceção para encontrar algumas informações limpas. solução, que é realmente o que acontece aqui ...

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

Agora todas as funções podem ser usadas. No exemplo a seguir, f(n)é avaliado para a função de identidade qualquer valor positivo de n:

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

Certamente, pode-se argumentar que as exceções não se destinam a ser usadas para redirecionar intencionalmente o intérprete (como um tipo de gotodeclaração ou provavelmente como um tipo de estilo de passagem de continuação), o que devo admitir. Mas, novamente, acho engraçada a ideia de usar tryuma única linha como uma returndeclaração: tentamos retornar algo (comportamento normal), mas não podemos fazê-lo por causa de uma chamada recursiva (exceção).

Resposta inicial (29/08/2013).

Eu escrevi um plugin muito pequeno para lidar com a recursão da cauda. Você pode encontrá-lo com minhas explicações aqui: https://groups.google.com/forum/?hl=fr#!topic/comp.lang.python/dIsnJ2BoBKs

Ele pode incorporar uma função lambda escrita com um estilo de recursão de cauda em outra função que a avaliará como um loop.

O recurso mais interessante nessa pequena função, na minha humilde opinião, é que a função não depende de algum truque de programação sujo, mas de mero cálculo lambda: o comportamento da função é alterado para outro quando inserido em outra função lambda que parece muito com o combinador Y.

A palavra Guido está em http://neopythonic.blogspot.co.uk/2009/04/tail-recursion-elimination.html

Recentemente, publiquei uma entrada no meu blog Histórico do Python sobre as origens dos recursos funcionais do Python. Uma observação lateral sobre não apoiar a eliminação da recursão da cauda (TRE) imediatamente provocou vários comentários sobre a pena que o Python não faz isso, incluindo links para entradas recentes do blog de outros que tentam "provar" que o TRE pode ser adicionado ao Python facilmente. Então, deixe-me defender minha posição (que é que eu não quero o TRE no idioma). Se você quer uma resposta curta, é simplesmente não-tônico. Aqui está a resposta longa:

O CPython não suporta e provavelmente nunca suportará a otimização da chamada de cauda com base nas declarações de Guido van Rossum sobre o assunto.

Ouvi argumentos de que isso torna a depuração mais difícil por causa de como ela modifica o rastreamento da pilha.

Experimente a implementação de TCO de macropia experimental para obter o tamanho.

Além de otimizar a recursão da cauda, ​​você pode definir a profundidade da recursão manualmente:

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