JavaScript로 재귀 이해

일부 문제는 재귀에 더 적합합니다. 예를 들어, 피보나치 시퀀스와 같은 서열은 재귀 정의를 갖는다. 순서의 각 숫자는 순서에서 처음 두 숫자의 합입니다. 트리 데이터 구조로 구축하거나 가로 지르는 문제는 재귀로 해결 될 수 있습니다. 재귀 적으로 생각하도록 스스로 훈련하면 그러한 문제를 해결하기 위해 강력한 기술을 제공 할 것입니다.

이 튜토리얼에서는 몇 가지 재귀 기능이 어떻게 작동하는지 단계별로 설명하고 재귀 함수를 체계적으로 정의하는 몇 가지 기술을 보여 드리겠습니다.

콘텐츠:

• 재귀 란 무엇입니까?
• 디지털 재귀
• 재귀 목록
• 목록을 작성하십시오
• 꼬리 재귀
• 요약

재귀 란 무엇입니까?

재귀 적으로 정의 된 함수는 단순화 된 버전 자체에 의해 정의 된 함수입니다. 간단한 예는 다음과 같습니다.

 기능 doa (n) {
    // ...
    if (n> 0) {
        DOA (N-1);
    }
}

재귀가 어떻게 작동하는지 개념적으로 이해하기 위해 코드 독립적 인 예를 살펴볼 것입니다. 회사의 전화에 응답 할 책임이 있다고 가정 해 봅시다. 이 회사는 바쁜 회사이므로 휴대 전화에는 여러 전화선이 있으므로 동시에 여러 전화를 처리 할 수 ​​있습니다. 각 전화선에는 핸드셋에 버튼이있어 들어오는 통화가있을 때 플래시됩니다. 오늘, 직장에 가서 전화를 켜면 동시에 4 개의 라인이 깜박입니다. 그래서 당신은 모든 전화에 응답하기 시작합니다.

당신은 첫 번째 줄을 들고 그들에게 다음과 같이 말합니다. "잠깐만 요." 다음으로, 당신은 세 번째 줄을 들고 대기에 넣습니다. 마지막으로, 각 통화를 마치면 이전 발신자로 돌아가서 해당 전화를 완료하고 전화를 끊습니다.

이 예제의 각 호출은 함수의 재귀 호출과 유사합니다. 통화를 받으면 통화 스택 (코드)에 넣습니다. 즉시 통화를 완료 할 수 없으면 대기에 전화를 걸었습니다. 기능 호출을 즉시 계산할 수없는 경우 통화 스택에 남아 있습니다. 전화에 응답 할 수 있으면 픽업됩니다. 코드가 함수 호출을 계산할 수 있으면 스택에서 튀어 나옵니다. 다음 코드 예제를 볼 때이 은유를 기억하십시오.

디지털 재귀

모든 재귀 함수는 종료 될 수 있도록 기본 사례가 필요합니다. 그러나 기본 케이스를 기능에 추가한다고해서 무한히 실행되는 것을 방지하지는 않습니다. 기능은 기본 상황에 더 가까이 다가 가기위한 단계가 있어야합니다. 이것은 재귀 단계입니다. 재귀 단계에서 문제는 더 작은 버전의 문제로 줄어 듭니다.

n에서 시작하는 모든 숫자를 곱한 함수가 있다고 가정합니다. 이것을 Factorial Function이라고합니다. N이 1과 같으면 4!로 씁니다.

각 단계에서 현재 번호에서 1을 빼게됩니다. 재귀 상황은 무엇입니까? 재귀 사례는 기능 사실 (4)입니다.

16. 4는 1과 같습니까? 아니요. 사실 (3).
17. 3은 1과 같습니까? 아니요. 사실 (2).
18. 2는 1과 같습니까? 아니요. 사실 (1).
19. 1은 1과 같습니까? 예. 사실 (2)을 반환하고 2를 반환합니다.
20. 3 * 사실 (2)은 사실 (4)이고 24를 반환합니다.

다음은 기능이 각 호출을 처리하는 방법을 확인하는 또 다른 방법입니다.

 <code>fact(4) 4 * fact(3) 4 * ( 3 * fact(2) ) 4 * ( 3 * ( 2 * fact(1) )) 4 * ( 3 * ( 2 * 1 ) ) 4 * ( 3 * 2 ) 4 * 6 24</code>

재귀적인 경우, 매개 변수는 변경되어 기본 사례에 더 가까워 야합니다. 이 매개 변수는 기본 사례에서 테스트해야합니다. 이전 예에서는 재귀 사례에서 1을 빼기 때문에 기본 경우에서는 매개 변수가 0인지 테스트합니다.

도전

1. 재귀 대신 루프를 사용하여 합 함수를 구현하십시오.
2. 두 숫자를 재귀 적으로 곱한 함수를 만듭니다. 예를 들어, 0; 그렇지 않으면 배열의 첫 번째 요소와 합 통화를 반환합니다.
3. 필터 기능을 단순화하여 목록에서 모든 항목을 제거합니다. 예를 들어, [ "a", "b", "d"].

꼬리 재귀

꼬리 재귀는 컴파일러가 TCO (Tail Call Optimization)를 수행하여 일반적인 재귀의 많은 성능 결함을 방지하는 재귀의 한 형태입니다. 또한 꼬리 재귀는 최대 기능 호출 깊이의 문제를 해결합니다. 그러나 어떻게 든 기능을 작성해야합니다.

꼬리 재귀는 함수 끝에서 재귀 함수를 호출하는 함수에 적합합니다. 예를 들어, 다음은 sum () 함수의 꼬리 재귀 버전입니다. sum ()의 전체 리턴 값은 전체 리턴 값이므로 런타임은 외부 함수를 안전하게 버리고 내부 기능의 결과 만 반환 할 수 있습니다. 그러나 많은 사람들이 다음과 같은 것을 여행 할 것입니다.

 function nottailrecursive (n) {
    // ...
    nottailrecursive (n) 1
}

재귀 함수가 끝에서 호출되기 때문에 이것이 꼬리 재귀를 사용한다고 생각할 수 있습니다. 그러나 그렇지 않습니다. JavaScript가 외부 함수로 돌아 가기 위해 1을 추가해야하기 때문입니다. 다시 작성할 수있는 방법 중 하나는 내부 기능이 해당 계산을 수행 할 수 있도록 인수로 1 전달하는 것입니다.

모든 브라우저가 현재 Tail Call 최적화를 지원하는 것은 아니지만 ES 표준에 있으므로 향후 더 많은 지원을 볼 수 있습니다. 또한 일반적으로 기능 매개 변수로 변경 사항을 분리하기 때문에 일반적으로 좋은 관행입니다.

도전

이 기사에서 예제 재귀 함수를 꼬리 재귀 함수로 재구성하십시오.

요약

재귀 함수에는 세 가지 부분이 있습니다. 첫 번째는 기본 상황이며,이 상황은 종료 조건입니다. 두 번째는 우리를 기본 상황에 더 가깝게하는 단계입니다. 세 번째는 재귀 단계이며, 여기서 함수는 단순화 된 입력으로 자체를 호출합니다.

재귀는 반복과 같습니다. 재귀 적으로 정의하거나 루프를 사용할 수있는 모든 함수. 재귀를 사용할 때 고려해야 할 다른 것들로는 재귀 중첩 목록과 최적화 된 재귀 호출이 포함됩니다.

재귀 함수를 재귀 함수로 리팩게 할 수있어 성능 장점을 제공 할 수 있습니다.

배우기를 계속하는 좋은 자료는 책 The Little Stander입니다. Q & A 형식을 사용하여 재귀 적으로 생각하는 방법을 가르쳐줍니다.

이 게시물은 Jacob Jackson의 기여로 업데이트되었습니다. Jacob은 웹 개발자, 기술 작가, 프리랜서 및 오픈 소스 기고자입니다.

위 내용은 JavaScript로 재귀 이해의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!