데코레이터를 사용하여 Python에서 꼬리 재귀 최적화

여기에서는 데코레이터를 사용하여 Python에서 꼬리 재귀를 최적화하는 방법을 보여주기 위해 일반적인 피보나치 수열을 사용합니다. 필요한 친구는

꼬리 재귀 소개
꼬리 재귀는 함수가 반환한 마지막 작업이 재귀 호출이고 그 다음에는 함수가 꼬리 재귀임을 의미합니다. 재귀는 선형입니다. 예를 들어 계승 함수가 호출될 때마다 스택을 지속적으로 푸시하여 새로운 스택(후입선출)이 생성되므로 스택 오버플로가 쉽게 발생할 수 있습니다. 꼬리 재귀는 현재 스택을 사용하여 데이터 적용 범위를 통해 재귀 기능을 최적화합니다.
팩토리얼 함수인 계승은 계산된 값을 전달하여 꼬리 재귀를 완료합니다. 그러나 Python에서는 컴파일러가 꼬리 재귀를 최적화하는 것을 허용하지 않으므로 재귀가 여러 번 반복되면 학습 목적으로 오류가 계속 보고됩니다.

예:

def factorial(n, x):
  if n == 0:
    return x
  else:
    return factorial(n-1, n*x)

print factorial(5, 1) # 120

꼬리 재귀 최적화여기서는 Fibo를 사용합니다. 홀수를 예로 들어 보겠습니다. 선형 재귀 알고리즘은 너무 비효율적이므로 먼저 호출하는 tail-pass 방법을 살펴보겠습니다.

(n,b1=1,b2=1,c=3):
 if n<3:
  return 1
 else:
  if n==c:
   return b1+b2
  else:
   return Fib(n,b1=b2,b2=b1+b2,c=c+1)

이 프로그램을 테스트하고 Fib(1001)을 호출해 보겠습니다. 결과는 다음과 같습니다.

>>> def Fib(n,b1=1,b2=1,c=3):

...  if n<3:

...   return 1

...  else:

...   if n==c:

...    return b1+b2

...   else:

...    return Fib(n,b1=b2,b2=b1+b2,c=c+1)

... 

>>> Fib(1001)

70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501L

>>>

Fib(1002)를 사용하면 결과는 커피입니다.

 .....

 File "<stdin>", line 8, in Fib

 File "<stdin>", line 8, in Fib

 File "<stdin>", line 8, in Fib

 File "<stdin>", line 8, in Fib

 File "<stdin>", line 8, in Fib

 File "<stdin>", line 8, in Fib

RuntimeError: maximum recursion depth exceeded

>>>

자, 이제 재귀 최적화를 마무리하겠습니다.

방금 Fib 함수에 데코레이터를 추가했습니다. , 다음과 같습니다:

@tail_call_optimized
def Fib(n,b1=1,b2=1,c=3):
 if n<3:
  return 1
 else:
  if n==c:
   return b1+b2
  else:
   return Fib(n,b1=b2,b2=b1+b2,c=c+1)

글쎄, 이 @tail_call_optimized 데코레이터를 사용하면 Python이 마술처럼 호출 스택의 한계를 깨뜨릴 수 있습니다. .

이제 Fib(20000)을 사용해도 780ms 안에 결과를 실행할 수 있습니다(780ms는 이전 블로그 포스팅에서 언급한 2000위안 넷북의 결과입니다)

거짓말이 아닙니다 , 이 마법의 코드를 살펴보겠습니다:

class TailRecurseException: 
 def __init__(self, args, kwargs): 
 self.args = args 
 self.kwargs = kwargs 
 
def tail_call_optimized(g): 
 """ 
 This function decorates a function with tail call 
 optimization. It does this by throwing an exception 
 if it is it's own grandparent, and catching such 
 exceptions to fake the tail call optimization. 
 
 This function fails if the decorated 
 function recurses in a non-tail context. 
 """ 
 def func(*args, **kwargs): 
 f = sys._getframe() 
 if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code: 
  raise TailRecurseException(args, kwargs) 
 else: 
  while 1: 
  try: 
   return g(*args, **kwargs) 
  except TailRecurseException, e: 
   args = e.args 
   kwargs = e.kwargs 
 func.__doc__ = g.__doc__ 
 return func

사용된 방법이 이전에 공개된 바 있습니다. 저자는 호출 스택의 증가를 막기 위해 예외를 발생시키고 스스로 잡아내는 방법을 사용했는데, 이는 정말 놀라운 일입니다. 더욱이 효율성 문제로 인해 직접 꼬리 재귀 Fib에 비해 약 5배의 시간 오버헤드가 발생합니다.

결국, 놀랍게도 꼬리 재귀 최적화라는 목표가 달성되었습니다.

Python에서 꼬리 재귀를 최적화하기 위해 데코레이터를 사용하는 것과 관련된 더 많은 기사를 보려면 PHP 중국어 웹사이트에 주목하세요!