꼬리 호출 최적화 (꼬리 재귀 및 연속 전달 스타일 모두 처리)를 수행하는 모듈을 게시했습니다. https://github.com/baruchel/tco

파이썬에서 꼬리 재귀 최적화

꼬리 재귀는 파이썬의 코딩 방식에 적합하지 않으며 루프에 포함시키는 방법에 신경 쓰지 않아야한다고 주장되었습니다. 나는이 견해로 논쟁하고 싶지 않다. 그러나 때로는 여러 가지 이유로 루프가 아닌 꼬리 재귀 함수로 새로운 아이디어를 시도하거나 구현하는 것을 좋아합니다 (프로세스가 아닌 아이디어에 초점을 맞추고 3 개의 “Pythonic”이 아니라 동시에 화면에 20 개의 짧은 기능이 있음) 기능, 내 코드 편집 등이 아닌 대화식 세션에서 작업).

파이썬에서 꼬리 재귀를 최적화하는 것은 실제로 매우 쉽습니다. 불가능하거나 매우 까다 롭다고 말하지만, 우아하고 짧고 일반적인 솔루션으로 달성 할 수 있다고 생각합니다. 심지어 이러한 솔루션의 대부분은 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

이것은 물론 함수의 단일 실제 목적입니다.

이 최적화로는 한 가지만 수행 할 수 없습니다. 다른 함수로 평가하는 꼬리 재귀 함수와 함께 사용할 수 없습니다 (이것은 호출 가능한 반환 객체가 모두 구별없이 추가 재귀 호출로 처리된다는 사실에서 비롯됩니다). 일반적으로 이러한 기능이 필요하지 않으므로 위의 코드에 매우 만족합니다. 그러나 더 일반적인 모듈을 제공하기 위해이 문제에 대한 해결 방법을 찾기 위해 조금 더 생각했습니다 (다음 섹션 참조).

이 프로세스의 속도와 관련하여 (그러나 실제 문제는 아님) 상당히 좋은 일입니다. tail-recursive 함수는 간단한 표현식을 사용하여 다음 코드보다 훨씬 빠르게 평가됩니다.

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

하나의 표현을 평가하는 것이 복잡한 경우조차도 몇 가지 간단한 표현을 평가하는 것보다 훨씬 빠르다고 생각합니다.이 두 번째 버전의 경우입니다. 나는이 새로운 기능을 내 모듈에 유지하지 않았으며, “공식적인”기능보다는 그것이 사용될 수있는 상황을 보지 못했다.

예외가있는 연속 전달 스타일

보다 일반적인 기능은 다음과 같습니다. 다른 함수를 반환하는 함수를 포함하여 모든 꼬리 재귀 함수를 처리 할 수 ​​있습니다. 재귀 호출은 예외를 사용하여 다른 반환 값에서 인식됩니다. 이 솔루션은 이전 솔루션보다 느립니다. 메인 루프에서 감지되는 “플래그”와 같은 특수 값을 사용하여 더 빠른 코드를 작성할 수는 있지만 특수 값이나 내부 키워드를 사용하는 아이디어는 마음에 들지 않습니다. 예외 사용에 대한 재미있는 해석이 있습니다 : 파이썬이 꼬리 재귀 호출을 좋아하지 않으면 꼬리 재귀 호출이 발생할 때 예외가 발생해야하며 파이썬 방식은 깨끗함을 찾기 위해 예외를 잡을 것입니다 솔루션은 실제로 여기에서 발생합니다 …

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 결합기와 매우 비슷합니다.

답변

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