Mam następujący fragment kodu, który nie działa z następującym błędem:

RuntimeError: przekroczona maksymalna głębokość rekurencji

Próbowałem przepisać to, aby umożliwić optymalizację rekurencji ogona (TCO). Uważam, że ten kod powinien był się udać, gdyby miało miejsce TCO.

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

print(trisum(1000, 0))

Czy powinienem dojść do wniosku, że Python nie wykonuje żadnego rodzaju TCO, czy po prostu muszę go definiować inaczej?

Nie, i nigdy nie będzie tak, ponieważ Guido van Rossum woli mieć odpowiednie ślady:

Eliminacja rekurencji ogona (2009-04-22)

Ostatnie słowa na ogonach (27.04.2009)

Możesz ręcznie wyeliminować rekurencję za pomocą takiej transformacji:

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

Opublikowałem moduł przeprowadzający optymalizację wywołania ogona (obsługujący zarówno styl rekurencji, jak i przekazywanie kontynuacji): https://github.com/baruchel/tco

Optymalizacja rekurencji ogona w Pythonie

Często twierdzono, że rekurencja ogona nie pasuje do Pythońskiego sposobu kodowania i że nie należy dbać o to, jak osadzić go w pętli. Nie chcę się kłócić z tym punktem widzenia; czasem jednak lubię próbować lub wdrażać nowe pomysły jako funkcje rekurencyjne zamiast z pętlami z różnych powodów (skupiając się raczej na pomyśle niż na procesie, mając na ekranie dwadzieścia krótkich funkcji zamiast tylko trzech „pytonicznych” funkcje, praca w interaktywnej sesji zamiast edycji mojego kodu itp.).

Optymalizacja rekurencji ogona w Pythonie jest w rzeczywistości dość łatwa. Chociaż mówi się, że jest to niemożliwe lub bardzo trudne, myślę, że można to osiągnąć za pomocą eleganckich, krótkich i ogólnych rozwiązań; Myślę nawet, że większość tych rozwiązań nie używa funkcji Pythona inaczej niż powinny. Czyste wyrażenia lambda współpracujące z bardzo standardowymi pętlami prowadzą do szybkich, wydajnych iw pełni użytecznych narzędzi do wdrażania optymalizacji rekurencji ogona.

Dla osobistej wygody napisałem mały moduł implementujący taką optymalizację na dwa różne sposoby. Chciałbym tutaj omówić moje dwie główne funkcje.

Prosty sposób: modyfikowanie kombinatora Y.

Syntezatora Y jest dobrze znane; pozwala na używanie funkcji lambda w sposób rekurencyjny, ale nie pozwala na osadzanie wywołań rekurencyjnych w pętli. Sam rachunek Lambda nie może zrobić czegoś takiego. Niewielka zmiana w kombinatorze Y może jednak ochronić wywołanie rekurencyjne, które ma zostać faktycznie ocenione. Ocena może zatem zostać opóźniona.

Oto słynne wyrażenie dla kombinatora Y:

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

Z niewielką zmianą mogłem uzyskać:

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

Zamiast wywoływać się sama, funkcja f zwraca teraz funkcję wykonującą to samo wywołanie, ale ponieważ ją zwraca, oceny można dokonać później z zewnątrz.

Mój kod to:

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

Z funkcji można skorzystać w następujący sposób; oto dwa przykłady z rekurencyjnymi wersjami silni i Fibonacciego:

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

Oczywiście głębokość rekurencji nie jest już problemem:

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

Jest to oczywiście jedyny prawdziwy cel tej funkcji.

Z tą optymalizacją nie można zrobić tylko jednej rzeczy: nie można jej używać z funkcją rekurencyjną ogonową przetwarzającą na inną funkcję (wynika to z faktu, że wszystkie zwracane obiekty, które można wywoływać, są obsługiwane jako kolejne rekurencyjne wywołania bez rozróżnienia). Ponieważ zwykle nie potrzebuję takiej funkcji, jestem bardzo zadowolony z powyższego kodu. Jednak w celu zapewnienia bardziej ogólnego modułu pomyślałem trochę więcej, aby znaleźć obejście tego problemu (patrz następny rozdział).

Jeśli chodzi o szybkość tego procesu (co nie jest jednak prawdziwym problemem), okazuje się, że jest całkiem dobry; funkcje rekurencyjne są sprawdzane nawet znacznie szybciej niż w przypadku następującego kodu przy użyciu prostszych wyrażeń:

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

Myślę, że ocena jednego wyrażenia, nawet skomplikowanego, jest znacznie szybsza niż ocena kilku prostych wyrażeń, co ma miejsce w drugiej wersji. Nie zachowałem tej nowej funkcji w moim module i nie widzę żadnych okoliczności, w których można by jej użyć, a nie „oficjalnej”.

Styl kontynuacji przejścia z wyjątkami

Oto bardziej ogólna funkcja; jest w stanie obsłużyć wszystkie funkcje rekurencyjne ogona, w tym te zwracające inne funkcje. Połączenia rekurencyjne są rozpoznawane na podstawie innych wartości zwracanych na podstawie wyjątków. To rozwiązanie jest wolniejsze niż poprzednie; szybszy kod może być prawdopodobnie napisany przy użyciu niektórych specjalnych wartości jako „flag” wykrywanych w głównej pętli, ale nie podoba mi się pomysł używania specjalnych wartości lub wewnętrznych słów kluczowych. Istnieje zabawna interpretacja używania wyjątków: jeśli Python nie lubi wywołań rekurencyjnych, należy zgłosić wyjątek, gdy nastąpi wywołanie rekurencyjne, a sposobem Pythona będzie przechwycenie wyjątku w celu znalezienia czystego rozwiązanie, które tak naprawdę dzieje się tutaj ...

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

Teraz można korzystać ze wszystkich funkcji. W poniższym przykładzie f(n)jest oceniane do funkcji tożsamości dla dowolnej dodatniej wartości n:

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

Oczywiście można argumentować, że wyjątki nie są przeznaczone do celowego przekierowywania tłumacza (jako rodzaj gotostwierdzenia lub raczej raczej stylu kontynuacji przejścia), co muszę przyznać. Ponownie uważam za zabawny pomysł używania trypojedynczego wiersza jako returnstwierdzenia: próbujemy coś zwrócić (normalne zachowanie), ale nie możemy tego zrobić z powodu wystąpienia wywołania rekurencyjnego (wyjątek).

Pierwsza odpowiedź (29.08.2013).

Napisałem bardzo małą wtyczkę do obsługi rekurencji ogona. Możesz go znaleźć z moimi wyjaśnieniami tam: https://groups.google.com/forum/?hl=fr#!topic/comp.lang.python/dIsnJ2BoBKs

Może osadzić funkcję lambda zapisaną stylem rekurencji ogona w innej funkcji, która oceni ją jako pętlę.

Moim skromnym zdaniem najciekawszą cechą tej małej funkcji jest to, że funkcja ta nie polega na jakimś brudnym hacku programistycznym, ale na rachunku lambda: zachowanie funkcji zmienia się na inne po wstawieniu do innej funkcji lambda, która wygląda bardzo podobnie do kombinatora Y.

Słowo Guido znajduje się na stronie http://neopythonic.blogspot.co.uk/2009/04/tail-recursion-elimination.html

Niedawno opublikowałem wpis na moim blogu Historia Pythona na temat pochodzenia funkcji funkcjonalnych Pythona. Uwaga boczna na temat nieobsługiwania eliminacji rekurencji ogona (TRE) natychmiast wywołała kilka komentarzy na temat tego, jak szkoda, że ​​Python tego nie robi, w tym linki do ostatnich wpisów na blogu innych osób próbujących „udowodnić”, że TRE można dodać do Pythona z łatwością. Więc pozwól mi bronić swojej pozycji (czyli tego, że nie chcę TRE w języku). Jeśli chcesz uzyskać krótką odpowiedź, jest ona po prostu niepytoniczna. Oto długa odpowiedź:

CPython nie wspiera i prawdopodobnie nigdy nie będzie wspierał optymalizacji ogonów na podstawie wypowiedzi Guido van Rossuma na ten temat.

Słyszałem argumenty, że utrudnia to debugowanie z powodu tego, jak modyfikuje ślad stosu.

Wypróbuj eksperymentalną implementację makropy TCO dla rozmiaru.

Oprócz optymalizacji rekurencji ogona, możesz ręcznie ustawić głębokość rekurencji poprzez:

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