Python 꼬리 귀속 최적화 실현 코드 및 원리 상세

전통적인 귀환에서 전형적인 모델은 첫 번째 귀환 호출을 실행한 다음에 다음 귀환을 호출해서 결과를 계산하는 것이다.이런 방식은 도중에 계산 결과를 얻지 못하고 모든 귀속 호출이 되돌아오는 것을 안다.이렇게 하면 코드 작성이 어느 정도 간결해졌지만 효율적으로 연결되기 어렵다.귀속이 깊어지면서 이전의 일부 변수는 저장하기 위해 창고를 분배해야 하기 때문이다.
꼬리 귀속은 전통적인 귀속에 비해 일종의 특례이다.마지막 귀속 중, 먼저 어떤 부분의 계산을 실행한 후에 귀속을 호출하기 시작하기 때문에, 당신은 현재의 계산 결과를 얻을 수 있으며, 이 결과도 매개 변수로 다음 귀속으로 전송될 것이다.즉, 함수 호출은 호출자 함수의 끝부분에 나타난다. 끝부분이기 때문에 전통적인 귀속보다 우수한 점은 어떤 국부 변수도 저장하지 않고 메모리 소모에서 절약 특성을 실현하는 데 있다.
다음은 컴퓨팅 덧셈의 인스턴스로 설명합니다.
우리는python으로 실현:
일반 반복 호출:

def recursion(n):
  if n==1:
    return n
  else:
    return n+recursion(n-1)

이 함수 recursion(5)을 호출하면 컴파일러가 실행합니다.
recursion(5)
5+recursion(4)
5+(4+recursion(3))
5+(4+(3+recursion(2)))
5+(4+(3+(2+recursion(1))))
5+(4+(3+(2+1)))
십오
이 컴파일러는 중간 결과를 저장하기 위해 귀속 창고를 분배합니다
다음 순서대로 진행합니다.

def tail_recursion(n,total=0):
  if n==0:
    return total
  else:
    return tail_recursion(n-1, total+n)

이때 컴파일러가 하는 작업:
tail_recursion(5,0)
tail_recursion(4,5)
tail_recursion(3,9)
tail_recursion(2,12)
tail_recursion(1,14)
tail_recursion(0,15)
십오
현재 시간의 계산 값이 두 번째 매개 변수로 다음 귀속으로 전달되어 시스템이 이전의 계산 결과를 보존할 필요가 없게 하는 것을 볼 수 있다.
후퇴의 우세는 명백히 알 수 있다.
그러나python 자체는 미귀환(미귀환에 최적화되지 않음)을 지원하지 않으며, 귀환 횟수에 제한이 있으며, 귀환 깊이가 1000을 넘으면 이상이 발생합니다.
각각recursion(998),tail_recursion(998,0)
출력:
498501
498501
문제 없음, 호출
recursion(999),tail_recursion(999,0)시,
출력: RuntimeError: 최대 재귀 깊이가 초과됨
귀속 횟수가 1000을 넘어섰기 때문에.
Python의 마지막 귀속을 위한 최적화 버전을 써서 Python이 귀속 호출 1000번의 제한을 돌파하도록 했습니다. Tail Call Optimization Decorator(Python recipe)
이상은 본문의 전체 내용입니다. 여러분의 학습에 도움이 되고 저희를 많이 응원해 주십시오.