JavaScript 재귀 및 루프 성능 비교 코드 분석

성능 측면에서 재귀는 루프에 비해 이점이 없습니다. 여러 함수 호출로 인한 오버헤드 외에도 재귀는 경우에 따라 불필요하게 반복되는 계산으로 이어질 수도 있습니다. 피보나치 수열을 계산하는 재귀 프로그램을 예로 들어 보겠습니다. n번째 항목 A(n)을 찾을 때 n-2번째 항목부터 시작하여 각 항목을 반복적으로 계산합니다. 항목 수가 적을수록 반복 횟수가 늘어납니다. B(i)를 i번째 항목이 계산된 횟수라고 하면

B(i)=1; i=n, ​​​​n-1

B(i)=B(i+ 1)+B(i+ 2); i
이런 식으로 B(i)는 흥미로운 역 피보나치 수열을 형성합니다. A(n)을 찾을 때 다음과 같습니다.

B(i)=A(n+1-i)

다른 관점에서 보면 C(i)를 A(i를 찾는 데 필요한 추가 개수라고 가정합니다. ), 그러면

C(i)=0; i=0, 1

C(i)=1+C(i-1)+C(i-1) i>1

Let D( i)=C (i)+1,

D(i)=1; i=0, 1

D(i)=D(i-1)+D(i-1)

so D (i) 피보나치 수열이 다시 형성됩니다. 그리고 다음과 같이 결론을 내릴 수 있습니다:

C(n)=A(n+1)-1

그리고 A(n)은 기하학적 급수로 증가합니다. n이 클 때 이 중복된 반복은 매우 위험해집니다. 루프를 사용하는 해당 프로그램은

B(n)=1; n은 임의의 값입니다.

C(n)=0; n=0, 1

C(n)=n>1

그래서 n이 크면 위에 주어진 루프를 사용하는 프로그램은 재귀를 사용하는 프로그램보다 훨씬 빠릅니다.

루프와 마찬가지로 재귀의 이 결함도 보완될 수 있습니다. 계산된 항만 기억하면 되고, 상위 항을 찾을 때 이전 항을 직접 읽어볼 수 있습니다. 이 기술은 재귀에서 흔히 사용되며 암기라고 합니다.

다음은 저장 기술을 이용하여 피보나치 수열을 찾는 재귀 알고리즘입니다.

아아아아

위 내용은 JavaScript 재귀 및 루프 성능 비교 코드 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!