꼬리 재귀

자신을 호출하는 함수를 재귀라고 합니다. 꼬리가 자신을 호출하는 경우 이를 꼬리 재귀라고 합니다.

재귀는 메모리를 많이 소모합니다. 수천 또는 수백 개의 호출 프레임을 동시에 저장해야 하고 "스택 오버플로" 오류가 쉽게 발생할 수 있기 때문입니다. 그러나 꼬리 재귀의 경우 호출 프레임이 하나만 있으므로 "스택 오버플로" 오류가 발생하지 않습니다.

예제 1

function factorial(n) {
  if (n === 1) return 1;  return n * factorial(n - 1);
}

factorial(5) // 120

로그인 후 복사

위 코드는 n의 계승 함수를 계산하기 위해서는 최대 n개의 통화 기록을 저장해야 하며 복잡도는 O(n)입니다.

꼬리 재귀로 다시 작성하면 호출 기록이 하나만 유지되며 복잡도는 O(1)

function factorial(n, total) {
  if (n === 1) return total;  return factorial(n - 1, n * total);
}

factorial(5, 1) // 120

로그인 후 복사

예제 2

피보나치 수열을 계산하는 더 유명한 예도 있는데, 이는 또한 완전히 설명할 수 있습니다. 꼬리 재귀 최적화의 중요성.

비꼬리 재귀 피보나치 수열은 다음과 같이 구현됩니다.

function Fibonacci (n) {
  if ( n <= 1 ) {return 1};  return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Fibonacci(10) // 89Fibonacci(100) // 堆栈溢出, 亲测页面直接卡死, cpu: i7-4720Fibonacci(500) // 堆栈溢出

로그인 후 복사

최적화 후

function Fibonacci2 (n , ac1 = 1 , ac2 = 1) {
  if( n <= 1 ) {return ac2};  return Fibonacci2 (n - 1, ac2, ac1 + ac2);
}

Fibonacci2(100) // 573147844013817200000Fibonacci2(1000) // 7.0330367711422765e+208 非一般的速度Fibonacci2(10000) // Infinity

로그인 후 복사

테일 재귀 최적화

테일 재귀 최적화는 엄격 모드에서만 적용됩니다. 그럼 일반 모드나 이 기능을 지원하지 않는 환경에서도 테일 재귀 최적화를 사용할 수 있는 방법이 있나요? 대답은 '예'입니다. 꼬리 재귀 최적화를 직접 구현하기만 하면 됩니다.

원리는 매우 간단합니다. 꼬리 재귀를 최적화해야 하는 이유는 호출 스택이 너무 많아 오버플로가 발생하기 때문입니다. 따라서 호출 스택을 줄이는 한 오버플로는 발생하지 않습니다. 호출 스택을 줄이려면 어떻게 해야 합니까? "재귀" 대신 "루프"를 사용하세요.

다음은 일반적인 재귀 함수입니다.

function sum(x, y) {
  if (y > 0) {    return sum(x + 1, y - 1);
  } else {    return x;
  }
}sum(1, 100000)// Uncaught RangeError: Maximum call stack size exceeded(…)

로그인 후 복사

위 코드에서 sum은 재귀 함수이고, 매개변수 x는 누적해야 하는 값, 매개변수 y는 재귀 횟수를 제어합니다. sum이 100,000번 반복되도록 지정되면 최대 호출 스택 횟수를 초과했음을 나타내는 오류가 보고됩니다.

트램폴린 함수는 재귀 실행을 순환 실행으로 변환할 수 있습니다.

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

로그인 후 복사

위는 함수 f를 매개변수로 받아들이는 트램폴린 함수의 구현입니다. f가 실행 후 함수를 반환하는 한 실행은 계속됩니다. 여기서는 함수 내부에서 함수를 호출하는 대신 함수를 반환한 다음 함수를 실행합니다. 이렇게 하면 재귀 실행이 방지되고 호출 스택이 너무 커지는 문제가 해결됩니다.

그런 다음 각 단계에서 다른 함수를 반환하도록 원래 재귀 함수를 다시 작성하기만 하면 됩니다.

function sum(x, y) {
  if (y > 0) {    return sum.bind(null, x + 1, y - 1);
  } else {    return x;
  }
}

로그인 후 복사

위 코드에서 sum 함수를 실행할 때마다 다른 버전의 함수가 반환됩니다.

이제 트램폴린 함수를 사용하여 sum을 실행할 때 호출 스택 오버플로가 발생하지 않습니다.

trampoline(sum(1, 100000))// 100001

로그인 후 복사

트램펄린 기능은 실제 꼬리 재귀 최적화가 아닙니다. 아래 구현은 입니다.

여기 핵심이 있습니다, 베테랑

function tco(f) {
  var value;  var active = false;  var accumulated = [];  return function accumulator() {
    accumulated.push(arguments);//每次将参数传入. 例如, 1 100000
    if (!active) {
      active = true;      
      while (accumulated.length) {//出循环条件, 当最后一次返回一个数字而不是一个函数时, accmulated已经被shift(), 所以出循环
        value = f.apply(this, accumulated.shift());//调用累加函数, 传入每次更改后的参数, 并执行
      }
      active = false;      
      return value;
    }
  };
}var sum = tco(function(x, y) {
  if (y > 0) {    
  return sum(x + 1, y - 1)//重点在这里, 每次递归返回真正函数其实还是accumulator函数
  }  
  else {    
  return x
  }
});

sum(1, 100000);//实际上现在sum函数就是accumulator函数// 100001

로그인 후 복사

위 코드에서 tco 함수는 꼬리 재귀 최적화의 구현이며 그 비밀은 활성 상태 변수에 있습니다. 기본적으로 이 변수는 비활성 상태입니다. 꼬리 재귀 최적화 프로세스가 시작되면 이 변수가 활성화됩니다. 그런 다음 각 재귀 합계 라운드는 정의되지 않은 값을 반환하므로 재귀 실행이 방지되고 누적된 배열은 각 합계 실행 라운드의 매개 변수를 저장하며 항상 가치가 있으므로 누산기 함수 내부의 while 루프가 항상 실행됩니다. 이러한 방식으로 "재귀"가 "루프"로 교묘하게 변경되고 다음 라운드의 매개변수가 이전 라운드의 매개변수를 대체하여 호출 스택의 레이어가 하나만 있도록 보장합니다.

위 내용은 JavaScript의 재귀적 스택 오버플로 오류 방지에 대한 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!