JavaScript 꼬리 귀속 최적화 탐색

원본 주소:https://github.com/HolyZheng/...
미조정 최적화
꼬리 재 귀 를 알 기 전에 우 리 는 무엇이 꼬리 호출 최적화 인지 까지 해 야 한다. 왜냐하면 꼬리 호출 최적화 가 꼬리 재 귀 의 기초 이기 때문이다.마지막 호출 은 함수 의 마지막 단계 에서 다른 함 수 를 호출 하 는 것 입 니 다.

function f() {
  return g()
}

ps: 마지막 단 계 는 다른 함 수 를 오래 호출 해 야 합 니 다. 상수 나 표현 식 이 아 닙 니 다. 예 를 들 어 returny 나 return g () + 1
꼬리 호출 최적화 의 원 리 는 무엇 입 니까?
완 일 봉 선생님 의 es6 함수 확장 에 따 르 면 함수 호출 은 메모리 에 '호출 기록' 을 형성 하고 '호출 프레임' (call frame) 이 라 고도 부 르 며 호출 위치 와 내부 변수 등 정 보 를 저장 합 니 다.함수 A 의 내부 호출 함수 B 가 있 으 면 A 의 호출 프레임 위 에 하나의 B 호출 프레임 이 형성 된다.B 운행 이 끝나 면 결 과 를 A 로 되 돌려 주 고 B 호출 프레임 이 사라 집 니 다.만약 함수 B 내부 에서 함수 C 를 호출 한다 면 C 의 호출 프레임 이 하나 더 있 을 것 이다.모든 호출 프레임 은 '호출 스 택' (call stack) 을 형성 합 니 다.
이곳 의 '호출 프레임' 과 '호출 스 택' 은 '실행 환경' 과 '역할 도 메 인 체인' 을 말 해 야 합 니 다.꼬리 호출 시 함수 의 마지막 조작 이기 때문에 외부 호출 프레임 을 유지 하지 않 고 외부 호출 프레임 을 직접 대체 할 필요 가 없 기 때문에 최적화 하 는 역할 을 할 수 있 습 니 다.
미 순환 최적화
우 리 는 재 귀 는 사용 하기에 편리 하지만 재 귀 는 함수 내부 에서 자신 을 호출 하 는 것 임 을 알 고 있 습 니 다. 재 귀 횟수 가 일정한 수량 급 에 이 르 렀 을 때 그 가 형성 한 호출 스 택 의 깊이 는 매우 무 섭 고 '스 택 넘 침' 오류 가 발생 할 수 있 습 니 다.꼬리 재 귀 최적화 란 꼬리 호출 최적화 의 원 리 를 이용 하여 재 귀 를 최적화 하 는 것 이다.흔히 볼 수 있 는 예 를 들 어 피 보 나치 수 치 를 구하 다.

function fibonacci (n) {
    return n <= 1 ? 1 : fibonacci(n - 1) + fibonacci(n - 2);
}

이 함 수 는 최적화 되 지 않 았 습 니 다. 콘 솔 에서 이 함 수 를 실행 할 때 fibonacci (40) 는 응답 이 느 린 문제 가 발생 했 습 니 다. fibonacci (50) 때 브 라 우 저 카드 가 죽 었 습 니 다.최적화 하 다.

function fibonacci (n, ac1, ac2) {
    (ac1 = ac1 || 1), (ac2 = ac2 || 1);
    return n <= 1 ? ac2 :fibonacci(n - 1, ac2, ac1 + ac2);
}

이 최 적 화 는 두 가지 점 이 있다. 먼저 알고리즘 상의 최 적 화 를 실 시 했 고 중복 되 는 계산 을 많이 줄 였 으 며 시간 복잡 도가 크게 낮 아 졌 다.두 번 째 는 꼬리 순환 최 적 화 를 실 시 했 는데 이치 에 따 르 면 '창고 넘 침' 이 발생 하지 않 을 것 이다.우 리 는 콘 솔 에 가서 다시 시도 할 수 있 습 니 다. 속도 의 향상 이 일반적인 속도 가 아니 라 첫 번 째 최적화 가 효력 이 발생 했다 는 것 을 증명 할 수 있 습 니 다. 그러나 우리 가 fibonacci (10000) 를 허용 할 때 잘못 보 고 했 습 니 다. Uncaught RangeError: Maximum call stack size exceeded 이것 은 우리 의 마지막 순환 최적화 가 효력 이 발생 하지 않 았 음 을 나타 냅 니 다.왜 일 까요?
제한성
위 에서 말 했 듯 이 우리 가 브 라 우 저의 콘 솔 에서 fibonacci (10000) 를 직접 실행 할 때 스 택 이 넘 쳤 습 니 다. 이것 은 왜 일 까요?이 점 에 대해 저 는 현재 자 료 를 조회 한 후에 이 해 를 하 겠 습 니 다. 비록 es6 는 꼬리 순환 최적화 를 실현 하 겠 다 고 제 안 했 지만 진정 으로 꼬리 순환 최적화 를 실현 한 브 라 우 저 는 많 지 않 습 니 다.그래서 우리 가 꼬리 재 귀 를 사용 하여 최적화 할 때 '스 택 넘 침' 의 오류 가 발생 했다.
트 램 펄 린 함수
그럼 어 떡 하지?우 리 는 마지막 순환 최적화 효 과 를 달성 하 는 또 다른 방법 이 있다. 그것 이 바로 사용 (trampoline) 이다.

function trampoline(f) {
  while (f && f instanceof Function) {
    f = f();
  }
  return f;
}

코드 가 새 함 수 를 되 돌려 주 는 것 으로 변경 되 었 습 니 다.

function fibonacci (n, ac1, ac2) {
    (ac1 = ac1 || 1), (ac2 = ac2 || 1);
    return n <= 1 ? ac2 :fibonacci.bind(null, n - 1, ac2, ac1 + ac2);
}

두 함수 가 결합 하면 재 귀 상 태 를 순환 으로 하고 스 택 이 넘 치 는 문제 도 해결 할 수 있 습 니 다.

trampoline(fibonacci (100000))
// Infinity