Python은 테일 재귀를 최적화합니까?

Python은 테일 재귀를 최적화합니까?

다음과 같은 에러가 발생하고 있는 코드가 있습니다.

RuntimeError: 최대 재귀 깊이를 초과했습니다.

Tail Recursion Optimization(TCO; 테일재귀최적화)을 가능하게 하기 위해 이것을 고쳐 쓰려고 했습니다.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에서 테일 재귀 최적화

꼬리 재귀는 피토닉의 코딩 방식에 맞지 않으며 어떻게 그것을 루프에 포함시키는지에 대해 신경 쓰지 말아야 한다고 종종 주장되어 왔다.나는 이 관점에 대해 논쟁하고 싶지 않다; 그러나 때때로 나는 다양한 이유로 루프보다는 테일 리커버리 기능으로 새로운 아이디어를 시도하거나 구현하는 것을 좋아한다(프로세스보다는 아이디어에 초점을 맞추고, 3개의 "피토닉" 기능보다 20개의 짧은 기능을 동시에 내 화면에 가지고 있다).즉, 코드를 편집하는 것이 아니라, 액티브한 세션입니다.

Python에서 테일 재귀를 최적화하는 것은 사실 매우 쉽습니다.불가능하거나 매우 까다롭다고는 하지만, 우아하고 짧고 일반적인 솔루션으로는 달성할 수 있다고 생각합니다.이러한 솔루션의 대부분은 Python의 기능을 필요로 하는 것 이외에는 사용하지 않는다고 생각합니다.매우 표준적인 루프와 함께 작동하는 깨끗한 람다 표현식은 테일 재귀 최적화를 구현하기 위한 빠르고 효율적이며 사용 가능한 도구로 이어집니다.

개인적인 편의를 위해 두 가지 방법으로 이러한 최적화를 구현하는 작은 모듈을 작성했습니다.저는 여기서 저의 두 가지 주요 기능에 대해 논의하고 싶습니다.

깔끔한 방법: Y combinator 변경

Y combinator는 잘 알려져 있습니다.이것은 람다 함수를 재귀적으로 사용할 수 있지만, 그 자체로는 재귀 콜을 루프에 포함시킬 수 없습니다.람다 미적분만으로는 그런 일을 할 수 없다.다만, Y combinator 를 약간 변경하는 것으로, 실제로 평가되는 재귀 콜을 보호할 수 있습니다.따라서 평가가 지연될 수 있습니다.

다음은 Y combinator의 유명한 표현입니다.

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이 테일 리커버리 콜을 좋아하지 않는 경우 테일 리커버리 콜이 발생했을 때 예외가 발생합니다.또, 피토닉의 방법은, 클린 솔루션을 찾기 위해서 예외를 잡는 것입니다.이것이 실제로 여기서 일어나고 있는 일입니다.

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 combinator와 매우 흡사한 다른 람다 함수에 삽입되면 다른 함수로 바뀝니다.

Guido는 http://neopythonic.blogspot.co.uk/2009/04/tail-recursion-elimination.html에 있습니다.

최근 Python History 블로그에 Python의 기능적 특징의 기원에 대한 글을 올렸습니다.TRE(Tail Recursion Elimation)를 지원하지 않는다는 부평은 Python이 이것을 하지 않는 것이 얼마나 유감스러운지에 대한 몇 가지 코멘트를 불러일으켰는데, 여기에는 TRE가 Python에 쉽게 추가될 수 있다는 것을 "증명"하려는 다른 사람들의 최근 블로그 엔트리에 대한 링크도 포함되어 있다.제 입장을 변호하겠습니다(즉, 저는 TRE를 언어로 하고 싶지 않습니다).짧은 대답을 원한다면, 그것은 단순히 비논리적이다.긴 답변은 다음과 같습니다.

CPython은 해당 주제에 대한 Guido van Rossum의 진술에 기초한 테일콜 최적화를 지원하지 않으며 앞으로도 지원하지 않을 것입니다.

스택 트레이스를 변경하는 방법 때문에 디버깅이 더 어려워진다는 주장을 들은 적이 있습니다.

테일 재귀 최적화 외에도 다음과 같이 재귀 깊이를 수동으로 설정할 수 있습니다.

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

규모에 따라 실험적인 매크로피 TCO 구현을 시도해 보십시오.

Python에는 테일 재귀 최적화가 내장되어 있지 않습니다.그러나 추상 구문 트리(AST)를 통해 함수를 "재구축"하여 재귀가 발생하지 않도록 하고 루프로 대체할 수 있습니다.Guido가 확실히 옳았습니다.이 방법에는 몇 가지 제한이 있기 때문에 사용을 추천할 수 없습니다.

다만, 트레이닝의 예라고는 할 수 없지만, Optimizer의 독자적인 버전을 쓰고 있기 때문에, 조작법도 시험해 볼 수 있습니다.

pip 경유로 이 패키지를 설치합니다.

pip install astrologic

이제 다음 샘플 코드를 실행할 수 있습니다.

from astrologic import no_recursion

counter = 0

@no_recursion
def recursion():
    global counter
    counter += 1
    if counter != 10000000:
        return recursion()
    return counter

print(recursion())

이 용액은 안정적이지 않기 때문에 절대 실가동 시에 사용해서는 안 됩니다.페이지에 기재되어 있는 중요한 제한 사항에 대해서는 github(러시아어, 죄송합니다)로 확인할 수 있습니다.그러나 이 솔루션은 코드 및 기타 유사한 트릭을 중단하지 않고 매우 "진짜"입니다.

언급URL : https://stackoverflow.com/questions/13591970/does-python-optimize-tail-recursion