함수로 돌아가서 더 깊이 연구해 보겠습니다.
첫 번째 주제는 재귀 입니다.
프로그래밍을 처음 접하는 사람이 아니라면 익숙할 것이므로 이 장을 건너뛰어도 됩니다.
재귀는 작업이 자연스럽게 동일한 종류의 여러 작업으로 분할될 수 있지만 더 간단한 상황에서 유용한 프로그래밍 패턴입니다. 또는 작업을 쉬운 작업과 동일한 작업의 더 간단한 변형으로 단순화할 수 있는 경우입니다. 또는 곧 살펴보겠지만 특정 데이터 구조를 처리하는 경우도 있습니다.
함수가 작업을 해결하면 그 과정에서 다른 많은 함수를 호출할 수 있습니다. 이것의 부분적인 경우는 함수가 자신을 호출하는 경우입니다. 이를 재귀 라고 합니다.
간단하게 시작하려면 x n 의 자연 거듭제곱으로 올리는 함수 pow(x, n) 작성해 보겠습니다. 즉, x n 번 곱합니다.
힘(2, 2) = 4 힘(2, 3) = 8 힘(2, 4) = 16
이를 구현하는 방법에는 두 가지가 있습니다.
반복적 사고: for 루프:
함수 pow(x, n) {
결과 = 1로 둡니다.
// 루프에서 결과에 x n 번 곱하기
for (let i = 0; i < n; i++) {
결과 *= x;
}
결과 반환;
}
경고( pow(2, 3) ); // 8재귀적 사고: 작업을 단순화하고 자기 호출:
함수 pow(x, n) {
if (n == 1) {
x를 반환;
} 또 다른 {
return x * pow(x, n - 1);
}
}
경고( pow(2, 3) ); // 8재귀 변형이 근본적으로 어떻게 다른지 참고하세요.
pow(x, n) 이 호출되면 실행이 두 가지 분기로 분할됩니다.
n==1 = x인 경우
/
pow(x, n) =
else = x * pow(x, n - 1) n == 1 이면 모든 것이 간단합니다. 이는 즉시 명백한 결과를 생성하기 때문에 재귀의 기본 이라고 합니다: pow(x, 1) x 와 같습니다.
그렇지 않으면 pow(x, n) x * pow(x, n - 1) 로 나타낼 수 있습니다. 수학에서는 x n = x * x n-1 이라고 씁니다. 이를 재귀 단계 라고 합니다. 작업을 더 간단한 작업( x 곱하기)과 동일한 작업에 대한 더 간단한 호출( n 이 낮은 pow )로 변환합니다. 다음 단계에서는 n 1 에 도달할 때까지 이를 더욱 단순화합니다.
pow n == 1 될 때까지 자신을 재귀적으로 호출한다고 말할 수도 있습니다.
예를 들어 pow(2, 4) 계산하기 위해 재귀 변형은 다음 단계를 수행합니다.
pow(2, 4) = 2 * pow(2, 3)
pow(2, 3) = 2 * pow(2, 2)
pow(2, 2) = 2 * pow(2, 1)
pow(2, 1) = 2
따라서 재귀는 결과가 명확해질 때까지 함수 호출을 더 간단한 것으로, 그리고 훨씬 더 간단한 것으로 축소하는 등의 작업을 계속합니다.
재귀는 일반적으로 더 짧습니다.
재귀 솔루션은 일반적으로 반복 솔루션보다 짧습니다.
여기서 조건 연산자 ? 사용하여 동일한 내용을 다시 작성할 수 있습니다. if 대신에 pow(x, n) 더 간결하고 읽기 쉽게 만드는 방법은 다음과 같습니다.
함수 pow(x, n) {
반환 (n == 1) ? x : (x * pow(x, n - 1));
} 최대 중첩 호출 수(첫 번째 호출 포함)를 재귀 깊이 라고 합니다. 우리의 경우에는 정확히 n 됩니다.
최대 재귀 깊이는 JavaScript 엔진에 의해 제한됩니다. 우리는 10000이라고 믿을 수 있고 일부 엔진은 더 많은 것을 허용하지만 100000은 아마도 대부분의 경우 한계를 벗어났습니다. 이를 완화하는 데 도움이 되는 자동 최적화(“테일 호출 최적화”)가 있지만 아직 모든 곳에서 지원되지 않으며 간단한 경우에만 작동합니다.
이는 재귀 적용을 제한하지만 여전히 매우 광범위합니다. 재귀적 사고 방식을 통해 코드가 더 간단해지고 유지 관리가 쉬워지는 작업이 많이 있습니다.
이제 재귀 호출이 어떻게 작동하는지 살펴보겠습니다. 이를 위해 우리는 함수의 내부를 살펴보겠습니다.
실행 중인 함수의 실행 프로세스에 대한 정보는 해당 실행 컨텍스트 에 저장됩니다.
실행 컨텍스트는 함수 실행에 대한 세부 정보를 포함하는 내부 데이터 구조입니다. 현재 제어 흐름이 있는 위치, 현재 변수, this 값(여기에서는 사용하지 않음) 및 기타 내부 세부 정보가 거의 없습니다.
하나의 함수 호출에는 정확히 하나의 실행 컨텍스트가 연결되어 있습니다.
함수가 중첩된 호출을 수행하면 다음이 발생합니다.
현재 기능이 일시 중지되었습니다.
이와 관련된 실행 컨텍스트는 실행 컨텍스트 스택 이라는 특수 데이터 구조에 기억됩니다.
중첩된 호출이 실행됩니다.
종료된 후에는 이전 실행 컨텍스트가 스택에서 검색되고 외부 함수는 중지된 위치에서 다시 시작됩니다.
pow(2, 3) 호출 중에 무슨 일이 일어나는지 살펴보겠습니다.
pow(2, 3) 호출이 시작될 때 실행 컨텍스트는 변수 x = 2, n = 3 저장하며 실행 흐름은 함수의 라인 1 에 있습니다.
다음과 같이 스케치할 수 있습니다.
컨텍스트: { x: 2, n: 3, 라인 1 } pow(2, 3)
이때 함수가 실행되기 시작합니다. 조건 n == 1 은 거짓이므로 흐름은 if 의 두 번째 분기로 계속됩니다.
함수 pow(x, n) {
if (n == 1) {
x를 반환;
} 또 다른 {
return x * pow(x, n - 1);
}
}
경고( pow(2, 3) );변수는 동일하지만 행이 변경되므로 이제 컨텍스트는 다음과 같습니다.
컨텍스트: { x: 2, n: 3, 5행 } pow(2, 3)
x * pow(x, n - 1) 계산하려면 새 인수 pow(2, 2) 사용하여 pow 의 하위 호출을 만들어야 합니다.
중첩된 호출을 수행하기 위해 JavaScript는 실행 컨텍스트 스택 에 현재 실행 컨텍스트를 기억합니다.
여기서는 동일한 함수 pow 호출하지만 전혀 중요하지 않습니다. 프로세스는 모든 기능에서 동일합니다.
현재 컨텍스트는 스택 상단에 "기억"됩니다.
하위 호출에 대한 새 컨텍스트가 생성됩니다.
하위 호출이 완료되면 이전 컨텍스트가 스택에서 팝되고 실행이 계속됩니다.
다음은 하위 호출 pow(2, 2) 입력했을 때의 컨텍스트 스택입니다.
컨텍스트: { x: 2, n: 2, 라인 1 } pow(2, 2)
컨텍스트: { x: 2, n: 3, 5행 } pow(2, 3)
새로운 현재 실행 컨텍스트는 맨 위에(굵게) 표시되고, 이전에 기억된 컨텍스트는 아래에 표시됩니다.
하위 호출을 마치면 변수와 중지된 코드의 정확한 위치를 모두 유지하므로 이전 컨텍스트를 다시 시작하기가 쉽습니다.
참고:
이 그림에서는 "line"이라는 단어를 사용합니다. 예에서는 한 줄에 하위 호출이 하나만 있지만 일반적으로 한 줄의 코드에는 pow(…) + pow(…) + somethingElse(…) 와 같이 여러 하위 호출이 포함될 수 있습니다. .
따라서 "하위 호출 직후" 실행이 재개된다고 말하는 것이 더 정확할 것입니다.
프로세스가 반복됩니다. 이제 x=2 , n=1 인수를 사용하여 새로운 하위 호출이 라인 5 에서 만들어집니다.
새로운 실행 컨텍스트가 생성되고 이전 컨텍스트가 스택 맨 위에 푸시됩니다.
컨텍스트: { x: 2, n: 1, 라인 1 } pow(2, 1)
컨텍스트: { x: 2, n: 2, 5행 } pow(2, 2)
컨텍스트: { x: 2, n: 3, 5행 } pow(2, 3)
현재 2개의 이전 컨텍스트가 있고 현재 pow(2, 1) 에 대해 1개가 실행 중입니다.
pow(2, 1) 실행 중에는 이전과 달리 조건 n == 1 이 참이므로 if 의 첫 번째 분기가 작동합니다.
함수 pow(x, n) {
if (n == 1) {
x를 반환;
} 또 다른 {
return x * pow(x, n - 1);
}
} 더 이상 중첩된 호출이 없으므로 함수가 완료되고 2 반환됩니다.
함수가 완료되면 실행 컨텍스트가 더 이상 필요하지 않으므로 메모리에서 제거됩니다. 이전 항목은 스택 상단에서 복원됩니다.
컨텍스트: { x: 2, n: 2, 5행 } pow(2, 2)
컨텍스트: { x: 2, n: 3, 5행 } pow(2, 3)
pow(2, 2) 의 실행이 재개됩니다. pow(2, 1) 하위 호출의 결과가 있으므로 x * pow(x, n - 1) 평가를 완료하여 4 반환할 수도 있습니다.
그런 다음 이전 컨텍스트가 복원됩니다.
컨텍스트: { x: 2, n: 3, 5행 } pow(2, 3)
완료되면 pow(2, 3) = 8 의 결과를 얻습니다.
이 경우 재귀 깊이는 3 입니다.
위 그림에서 볼 수 있듯이 재귀 깊이는 스택의 최대 컨텍스트 수와 같습니다.
메모리 요구사항을 참고하세요. 컨텍스트는 메모리를 사용합니다. 우리의 경우 n 의 거듭제곱을 올리려면 실제로 n 의 모든 낮은 값에 대해 n 컨텍스트에 대한 메모리가 필요합니다.
루프 기반 알고리즘은 메모리를 더 절약합니다.
함수 pow(x, n) {
결과 = 1로 둡니다.
for (let i = 0; i < n; i++) {
결과 *= x;
}
결과 반환;
} 반복적 pow i 변경하는 단일 컨텍스트를 사용하여 프로세스를 result . 메모리 요구 사항은 작고 고정되어 있으며 n 에 의존하지 않습니다.
모든 재귀는 루프로 다시 작성될 수 있습니다. 일반적으로 루프 변형을 더 효과적으로 만들 수 있습니다.
...그러나 때때로 재작성이 사소한 것이 아닐 때가 있습니다. 특히 함수가 조건에 따라 다른 재귀 하위 호출을 사용하고 그 결과를 병합하거나 분기가 더 복잡할 때 더욱 그렇습니다. 그리고 최적화는 불필요할 수도 있고 노력할 가치가 전혀 없을 수도 있습니다.
재귀는 더 짧은 코드를 제공하고 이해하기 쉽고 지원하기 쉽습니다. 모든 곳에서 최적화가 필요한 것은 아니며 대부분 좋은 코드가 필요하므로 사용됩니다.
재귀의 또 다른 훌륭한 적용은 재귀 순회입니다.
상상해 보세요. 우리 회사가 있습니다. 직원 구조는 객체로 표시될 수 있습니다.
회사 = {
판매량: [{
이름: '존',
급여 : 1000
}, {
이름: '앨리스',
급여 : 1600
}],
개발: {
사이트: [{
이름: '피터',
급여 : 2000
}, {
이름: '알렉스',
급여 : 1800
}],
내부: [{
이름: '잭',
급여 : 1300
}]
}
};즉, 회사에는 부서가 있습니다.
부서에는 다양한 직원이 있을 수 있습니다. 예를 들어 sales 부서에는 John과 Alice라는 두 명의 직원이 있습니다.
또는 development sites 와 internals 두 가지 분기가 있는 것처럼 부서가 하위 부서로 분할될 수도 있습니다. 그들 각각은 자신의 직원을 가지고 있습니다.
하위 부서가 성장하면 하위 하위 부서(또는 팀)로 분할되는 것도 가능합니다.
예를 들어, 향후 sites 부서는 siteA 및 siteB 팀으로 분할될 수 있습니다. 그리고 잠재적으로 더 많이 분할될 수도 있습니다. 사진에는 없지만 참고만 하시면 됩니다.
이제 모든 급여의 합계를 구하는 함수가 필요하다고 가정해 보겠습니다. 어떻게 그렇게 할 수 있나요?
반복적인 접근은 구조가 단순하지 않기 때문에 쉽지 않습니다. 첫 번째 아이디어는 첫 번째 수준 부서에 중첩된 하위 루프가 있는 company 에 대한 for 루프를 만드는 것일 수 있습니다. 하지만 sites 와 같은 2차 수준 부서의 직원을 반복하려면 더 많은 중첩된 하위 루프가 필요합니다. 그리고 나중에 나타날 수 있는 3차 수준 부서의 내부에 또 다른 하위 루프가 있습니까? 단일 객체를 순회하기 위해 코드에 3~4개의 중첩 하위 루프를 넣으면 다소 보기 흉해집니다.
재귀를 시도해 봅시다.
보시다시피, 우리 함수가 부서를 합산할 때 두 가지 가능한 경우가 있습니다.
여러 사람들로 구성된 "간단한" 부서라면 간단한 루프로 급여를 합산할 수 있습니다.
또는 N 하위 부서가 있는 객체 인 경우 N 재귀 호출을 수행하여 각 하위 부서에 대한 합계를 얻고 결과를 결합할 수 있습니다.
첫 번째 경우는 배열을 얻을 때 재귀의 기본, 사소한 경우입니다.
객체를 얻는 두 번째 경우는 재귀 단계입니다. 복잡한 작업은 소규모 부서의 하위 작업으로 분할됩니다. 그들은 차례로 다시 분할될 수 있지만 조만간 분할은 (1)에서 완료됩니다.
알고리즘은 코드에서 읽기가 더 쉬울 것입니다.
let company = { // 동일한 객체, 간결성을 위해 압축됨
sales: [{이름: 'John', 급여: 1000}, {이름: 'Alice', 급여: 1600 }],
개발: {
사이트: [{이름: '피터', 급여: 2000}, {이름: 'Alex', 급여: 1800 }],
내부: [{이름: 'Jack', 급여: 1300}]
}
};
// 작업을 수행하는 함수
함수 sumSalaries(부서) {
if (Array.isArray(department)) { // 사례 (1)
return Department.reduce((prev, current) => prev + current.salary, 0); // 배열 합산
} else { // 사례(2)
합계 = 0으로 둡니다.
for (Object.values(department)의 하위 부서하자) {
합계 += sumSalaries(subdep); // 하위 부서를 재귀적으로 호출하고 결과를 합산합니다.
}
반환 금액;
}
}
Alert(sumSalaries(회사)); // 7700코드는 짧고 이해하기 쉽습니다(아마도?). 이것이 바로 재귀의 힘입니다. 또한 모든 수준의 하위 부서 중첩에도 작동합니다.
통화 다이어그램은 다음과 같습니다.
우리는 원칙을 쉽게 볼 수 있습니다. 객체 {...} 에 대해 하위 호출이 수행되는 반면 배열 [...] 은 재귀 트리의 "잎"이므로 즉각적인 결과를 제공합니다.
코드는 이전에 다룬 스마트 기능을 사용합니다.
arr.reduce 메소드는 배열의 합을 구하는 배열 메소드 장에서 설명했습니다.
for(val of Object.values(obj)) 를 반복하여 객체 값을 반복합니다. Object.values 해당 값의 배열을 반환합니다.
재귀적(재귀적으로 정의된) 데이터 구조는 부분적으로 자체를 복제하는 구조입니다.
우리는 위의 회사 구조의 예에서 이를 보았습니다.
회사 부서는 다음과 같습니다.
사람들의 배열.
또는 부서가 있는 개체입니다.
웹 개발자에게는 훨씬 더 잘 알려진 예가 있습니다: HTML 및 XML 문서.
HTML 문서에서 HTML 태그 에는 다음 목록이 포함될 수 있습니다.
텍스트 조각.
HTML 주석.
기타 HTML 태그 (텍스트 조각/주석 또는 기타 태그 등이 포함될 수 있음)
그것은 다시 한 번 재귀적인 정의입니다.
더 나은 이해를 위해 경우에 따라 배열에 대한 더 나은 대안이 될 수 있는 "연결된 목록"이라는 재귀 구조를 하나 더 다룰 것입니다.
순서가 지정된 개체 목록을 저장하고 싶다고 상상해 보세요.
자연스러운 선택은 배열입니다.
arr = [obj1, obj2, obj3];
…하지만 배열에 문제가 있습니다. "요소 삭제" 및 "요소 삽입" 작업은 비용이 많이 듭니다. 예를 들어, arr.unshift(obj) 작업은 새로운 obj 위한 공간을 확보하기 위해 모든 요소의 번호를 다시 매겨야 하며, 배열이 크면 시간이 걸립니다. arr.shift() 와 동일합니다.
대량 번호 다시 매기기가 필요하지 않은 유일한 구조적 수정은 배열 끝에서 작동하는 수정 arr.push/pop 입니다. 따라서 처음부터 작업해야 할 때 큰 대기열의 경우 배열이 상당히 느려질 수 있습니다.
또는 빠른 삽입/삭제가 정말로 필요한 경우 연결 목록이라는 다른 데이터 구조를 선택할 수 있습니다.
연결된 목록 요소는 다음을 사용하여 객체로 재귀적으로 정의됩니다.
value .
next 연결된 목록 요소를 참조하는 다음 속성이거나 그것이 끝이면 null 입니다.
예를 들어:
목록 = {
값: 1,
다음: {
값: 2,
다음: {
값: 3,
다음: {
값: 4,
다음: null
}
}
}
};목록의 그래픽 표현:
생성을 위한 대체 코드:
목록 = {값: 1 };
list.next = { 값: 2 };
list.next.next = { 값: 3 };
list.next.next.next = { 값: 4 };
목록.next.next.next.next = null; 여기서 우리는 여러 개체가 있고 각 개체에는 value 있고 next 이웃을 가리키는 개체가 있다는 것을 더욱 명확하게 볼 수 있습니다. list 변수는 체인의 첫 번째 개체이므로 next 포인터를 따라가면 모든 요소에 접근할 수 있습니다.
목록은 쉽게 여러 부분으로 분할하고 나중에 다시 결합할 수 있습니다.
let secondList = list.next.next; 목록.다음.다음 = null;
가입하려면:
list.next.next = 두 번째목록;
그리고 확실히 우리는 어느 곳에든 항목을 삽입하거나 제거할 수 있습니다.
예를 들어, 새 값을 앞에 추가하려면 목록의 헤드를 업데이트해야 합니다.
목록 = {값: 1 };
list.next = { 값: 2 };
list.next.next = { 값: 3 };
list.next.next.next = { 값: 4 };
// 목록에 새 값을 추가합니다.
list = { value: "새 항목", next: 목록 }; 중간에서 값을 제거하려면 이전 값의 next 값을 변경하십시오.
목록.다음 = 목록.다음.다음;
우리는 list.next 1 넘어 값 2 로 점프하도록 했습니다. 이제 값 1 이 체인에서 제외됩니다. 다른 곳에 저장되어 있지 않으면 자동으로 메모리에서 제거됩니다.
배열과 달리 대량으로 번호를 다시 매길 필요가 없으며 요소를 쉽게 재배열할 수 있습니다.
당연히 목록이 항상 배열보다 나은 것은 아닙니다. 그렇지 않으면 모든 사람이 목록만 사용할 것입니다.
가장 큰 단점은 번호로 요소에 쉽게 액세스할 수 없다는 것입니다. 쉬운 배열에서는 arr[n] 이 직접 참조입니다. 하지만 목록에서는 첫 번째 항목부터 시작하여 next 항목으로 N 번 이동하여 N번째 요소를 가져와야 합니다.
…하지만 항상 그런 작업이 필요한 것은 아닙니다. 예를 들어 큐나 데크가 필요할 때 양쪽 끝에서 요소를 매우 빠르게 추가/제거할 수 있어야 하지만 중간에 대한 액세스는 필요하지 않은 정렬된 구조입니다.
목록을 향상할 수 있습니다.
이전 요소를 참조하기 위해 next 외에 prev 속성을 추가하여 쉽게 뒤로 이동할 수 있습니다.
목록의 마지막 요소를 참조하는 tail 이라는 변수를 추가할 수도 있습니다(그리고 끝에서 요소를 추가/제거할 때 이를 업데이트합니다).
…데이터 구조는 필요에 따라 달라질 수 있습니다.
자귀:
재귀는 함수 자체를 호출하는 것을 의미하는 프로그래밍 용어입니다. 재귀 함수를 사용하면 우아한 방식으로 작업을 해결할 수 있습니다.
함수가 자신을 호출하는 것을 재귀 단계 라고 합니다. 재귀의 기본은 함수가 더 이상 호출을 하지 않도록 작업을 매우 단순하게 만드는 함수 인수입니다.
재귀적으로 정의된 데이터 구조는 그 자체를 사용하여 정의할 수 있는 데이터 구조입니다.
예를 들어 연결된 목록은 목록(또는 null)을 참조하는 객체로 구성된 데이터 구조로 정의될 수 있습니다.
목록 = { 값, 다음 -> 목록 }이 장의 HTML 요소 트리나 부서 트리와 같은 트리도 자연스럽게 재귀적입니다. 트리에는 분기가 있고 모든 분기에는 다른 분기가 있을 수 있습니다.
sumSalary 예제에서 본 것처럼 재귀 함수를 사용하여 이를 살펴볼 수 있습니다.
모든 재귀 함수는 반복 함수로 다시 작성할 수 있습니다. 때로는 물건을 최적화하는 데 필요한 경우도 있습니다. 그러나 많은 작업의 경우 재귀 솔루션이 충분히 빠르고 작성 및 지원이 더 쉽습니다.
중요도: 5
숫자 1 + 2 + ... + n 의 합을 계산하는 함수 sumTo(n) 작성하세요.
예를 들어:
합계(1) = 1 sumTo(2) = 2 + 1 = 3 sumTo(3) = 3 + 2 + 1 = 6 sumTo(4) = 4 + 3 + 2 + 1 = 10 ... 합계(100) = 100 + 99 + ... + 2 + 1 = 5050
3가지 솔루션 변형을 만듭니다.
for 루프를 사용합니다.
재귀를 사용하면 n > 1 인 경우 sumTo(n) = n + sumTo(n-1) 이 발생합니다.
산술 진행 공식을 사용합니다.
결과의 예:
function sumTo(n) { /*... 코드 ... */ }
경고(sumTo(100) ); // 5050PS 어떤 솔루션 변형이 가장 빠른가요? 가장 느린가요? 왜?
PPS sumTo(100000) 계산하기 위해 재귀를 사용할 수 있습니까?
루프를 사용하는 솔루션:
함수 sumTo(n) {
합계 = 0으로 둡니다.
for (let i = 1; i <= n; i++) {
합계 += i;
}
반환 금액;
}
경고(sumTo(100) );재귀를 사용한 솔루션:
함수 sumTo(n) {
(n == 1)인 경우 1을 반환합니다.
return n + sumTo(n - 1);
}
경고(sumTo(100) ); 공식을 사용한 해법: sumTo(n) = n*(n+1)/2 :
함수 sumTo(n) {
n * (n + 1) / 2를 반환합니다.
}
경고(sumTo(100) ); PS 당연히 공식이 가장 빠른 솔루션입니다. 임의의 숫자 n 에 대해 3개의 연산만 사용합니다. 수학이 도움이 됩니다!
루프 변형은 속도 측면에서 두 번째입니다. 재귀와 루프 변형 모두에서 동일한 숫자를 합산합니다. 그러나 재귀에는 중첩 호출 및 실행 스택 관리가 포함됩니다. 또한 리소스가 필요하므로 속도가 느려집니다.
PPS 일부 엔진은 "테일 호출" 최적화를 지원합니다. 재귀 호출이 함수의 가장 마지막 호출이고 다른 계산이 수행되지 않은 경우 외부 함수는 실행을 재개할 필요가 없으므로 엔진은 다음을 수행할 필요가 없습니다. 실행 컨텍스트를 기억하세요. 이는 메모리에 대한 부담을 제거합니다. 그러나 JavaScript 엔진이 테일 호출 최적화를 지원하지 않는 경우(대부분은 그렇지 않음) 오류가 발생합니다. 최대 스택 크기가 초과되었습니다. 일반적으로 총 스택 크기에 제한이 있기 때문입니다.
중요도: 4
자연수의 계승은 숫자에 "number minus one" 을 곱한 다음 "number minus two" 곱한 다음 1 될 때까지 계속됩니다. n 의 계승은 n!
계승의 정의를 다음과 같이 작성할 수 있습니다:
N! = n * (n - 1) * (n - 2) * ...*1
다양한 n 에 대한 계승 값:
1! = 1 2! = 2 * 1 = 2 3! = 3 * 2 * 1 = 6 4! = 4 * 3 * 2 * 1 = 24 5! = 5 * 4 * 3 * 2 * 1 = 120
작업은 n! 계산하는 함수 factorial(n) 작성하는 것입니다! 재귀 호출을 사용합니다.
경고(factorial(5)); // 120
추신 힌트: n! n * (n-1)! 예를 들면: 3! = 3*2! = 3*2*1! = 6
정의에 따르면 계승 n! n * (n-1)! .
즉, factorial(n) 의 결과는 n 에 factorial(n-1) 의 결과를 곱하여 계산할 수 있습니다. 그리고 n-1 에 대한 호출은 1 될 때까지 반복적으로 더 낮아지고 낮아질 수 있습니다.
함수 계승(n) {
반환 (n != 1) ? n * 계승(n - 1) : 1;
}
경고(factorial(5)); // 120 재귀의 기본은 값 1 입니다. 여기서는 0 기본으로 만들 수도 있습니다. 크게 중요하지는 않지만 재귀 단계를 하나 더 제공합니다.
함수 계승(n) {
n을 반환 ? n * 계승(n - 1) : 1;
}
경고(factorial(5)); // 120중요도: 5
피보나치 수열의 공식은 F n = F n-1 + F n-2 입니다. 즉, 다음 숫자는 이전 두 숫자의 합입니다.
처음 두 숫자는 1 , 다음 2(1+1) , 그 다음 3(1+2) , 5(2+3) 등입니다: 1, 1, 2, 3, 5, 8, 13, 21... .
피보나치 수는 황금비 및 우리 주변의 많은 자연 현상과 관련이 있습니다.
n-th 피보나치 수를 반환하는 함수 fib(n) 을 작성하세요.
작업의 예:
function fib(n) { /* 코드 */ }
경고(fib(3)); // 2
경고(fib(7)); // 13
경고(fib(77)); // 5527939700884757 PS 함수는 빨라야 합니다. fib(77) 에 대한 호출은 1초도 채 걸리지 않습니다.
여기서 시도할 수 있는 첫 번째 솔루션은 재귀 솔루션입니다.
피보나치 수는 정의상 재귀적입니다.
함수 fib(n) {
n <= 1을 반환합니까? n : fib(n - 1) + fib(n - 2);
}
경고( fib(3) ); // 2
경고( fib(7) ); // 13
// fib(77); // 매우 느릴 것입니다! …하지만 n 값이 크면 속도가 매우 느려집니다. 예를 들어, fib(77) 모든 CPU 리소스를 먹어치워 한동안 엔진을 중단시킬 수 있습니다.
그 이유는 함수가 하위 호출을 너무 많이 만들기 때문입니다. 동일한 값이 계속해서 재평가됩니다.
예를 들어 fib(5) 에 대한 계산을 살펴보겠습니다.
... fib(5) = fib(4) + fib(3) fib(4) = fib(3) + fib(2) ...
여기서 우리는 fib(5) 와 fib(4) 모두에 fib(3) 값이 필요하다는 것을 알 수 있습니다. 따라서 fib(3) 완전히 독립적으로 두 번 호출되고 평가됩니다.
전체 재귀 트리는 다음과 같습니다.
fib(3) 두 번 평가되고 fib(2) 는 세 번 평가된다는 것을 분명히 알 수 있습니다. 총 계산량은 n 보다 훨씬 빠르게 증가하므로 n=77 인 경우에도 엄청납니다.
이미 평가된 값을 기억함으로써 이를 최적화할 수 있습니다. fib(3) 값이 한 번 계산되면 향후 계산에서 이를 재사용할 수 있습니다.
또 다른 변형은 재귀를 포기하고 완전히 다른 루프 기반 알고리즘을 사용하는 것입니다.
n 에서 더 낮은 값으로 이동하는 대신 1 과 2 에서 시작하여 fib(3) 합으로 얻은 다음 fib(4) 이전 두 값의 합으로 얻은 다음 fib(5) 얻는 루프를 만들 수 있습니다. 필요한 값에 도달할 때까지 계속해서 올라갑니다. 각 단계에서 이전 값 두 개만 기억하면 됩니다.
새로운 알고리즘의 세부 단계는 다음과 같습니다.
시작:
// a = fib(1), b = fib(2), 이 값은 정의에 따라 1입니다. a = 1, b = 1이라고 가정합니다. // c = fib(3)을 합으로 얻습니다. c = a + b라고 하자; /* 이제 fib(1), fib(2), fib(3)이 있습니다. a b c 1, 1, 2 */
이제 우리는 fib(4) = fib(2) + fib(3) 을 얻고 싶습니다.
변수를 이동해 보겠습니다. a,b fib(2),fib(3) 얻고 c 해당 합계를 얻습니다.
a = b; // 이제 a = fib(2) b = c; // 이제 b = fib(3) c = a + b; // c = fib(4) /* 이제 시퀀스가 생겼습니다: a b c 1, 1, 2, 3 */
다음 단계에서는 또 다른 시퀀스 번호를 제공합니다.
a = b; // 이제 a = fib(3)
b = c; // 이제 b = fib(4)
c = a + b; // c = fib(5)
/* 이제 순서는 다음과 같습니다(숫자가 하나 더 있음).
a b c
1, 1, 2, 3, 5
*/…필요한 값을 얻을 때까지 계속합니다. 이는 재귀보다 훨씬 빠르며 중복 계산이 필요하지 않습니다.
전체 코드:
함수 fib(n) {
a = 1이라고 하자;
b = 1이라고 하자;
for (let i = 3; i <= n; i++) {
c = a + b라고 하자;
a = b;
b = c;
}
b를 반환;
}
경고( fib(3) ); // 2
경고( fib(7) ); // 13
경고( fib(77) ); // 5527939700884757 루프는 i=3 으로 시작합니다. 첫 번째와 두 번째 시퀀스 값이 변수 a=1 , b=1 에 하드 코딩되어 있기 때문입니다.
이 접근 방식을 동적 프로그래밍 상향식이라고 합니다.
중요도: 5
(재귀 및 스택 장에서 설명한 대로) 단일 연결 목록이 있다고 가정해 보겠습니다.
목록 = {
값: 1,
다음: {
값: 2,
다음: {
값: 3,
다음: {
값: 4,
다음: null
}
}
}
}; 목록 항목을 하나씩 출력하는 함수 printList(list) 작성하세요.
루프 사용과 재귀 사용이라는 두 가지 솔루션 변형을 만듭니다.
재귀를 사용하는 것과 사용하지 않는 것 중 더 나은 점은 무엇입니까?
루프 기반 솔루션 변형:
목록 = {
값: 1,
다음: {
값: 2,
다음: {
값: 3,
다음: {
값: 4,
다음: null
}
}
}
};
함수 printList(목록) {
tmp = 목록을 보자;
동안(tmp) {
경고(tmp.value);
tmp = tmp.next;
}
}
printList(목록); 목록을 살펴보기 위해 임시 변수 tmp 사용한다는 점에 유의하세요. 기술적으로는 함수 매개변수 list 대신 사용할 수 있습니다.
함수 printList(목록) {
동안(목록) {
경고(목록.값);
목록 = 목록.다음;
}
} …하지만 그건 현명하지 못한 일이겠죠. 미래에는 기능을 확장하고 목록을 사용하여 다른 작업을 수행해야 할 수도 있습니다. list 변경하면 그러한 기능을 잃게 됩니다.
좋은 변수 이름에 대해 이야기하면 여기서 list 목록 자체입니다. 그것의 첫 번째 요소. 그리고 그 상태로 유지되어야 합니다. 그것은 명확하고 신뢰할 수 있습니다.
반면에 tmp 의 역할은 for 루프의 i 처럼 독점적으로 목록 순회입니다.
printList(list) 의 재귀 변형은 간단한 논리를 따릅니다. 목록을 출력하려면 현재 요소 list 출력해야 하며, 그런 다음 list.next 에 대해서도 동일한 작업을 수행합니다.
목록 = {
값: 1,
다음: {
값: 2,
다음: {
값: 3,
다음: {
값: 4,
다음: null
}
}
}
};
함수 printList(목록) {
경고(목록.값); // 현재 항목을 출력합니다.
if (list.next) {
printList(list.next); // 나머지 목록에도 동일한 작업을 수행합니다.
}
}
printList(목록);이제 무엇이 더 나아졌나요?
기술적으로는 루프가 더 효과적입니다. 이 두 가지 변형은 동일하지만 루프는 중첩된 함수 호출에 리소스를 소비하지 않습니다.
반면에 재귀 변형은 더 짧고 때로는 이해하기 쉽습니다.
중요도: 5
이전 작업에서 단일 연결 목록을 출력합니다. 단일 연결 목록을 역순으로 출력합니다.
루프 사용과 재귀 사용이라는 두 가지 솔루션을 만드십시오.
여기서 재귀 논리는 약간 까다롭습니다.
먼저 목록의 나머지 부분을 출력한 다음 현재 목록을 출력해야 합니다.
목록 = {
값: 1,
다음: {
값: 2,
다음: {
값: 3,
다음: {
값: 4,
다음: null
}
}
}
};
함수 printReverseList(목록) {
if (list.next) {
printReverseList(list.next);
}
경고(목록.값);
}
printReverseList(목록);
루프 변형은 직접 출력보다 약간 더 복잡합니다.
list 의 마지막 값을 얻을 수 있는 방법은 없습니다. 우리는 또한 “돌아갈” 수도 없습니다.
따라서 우리가 할 수 있는 일은 먼저 항목을 직접 순서로 살펴보고 배열로 기억한 다음 기억한 내용을 역순으로 출력하는 것입니다.
목록 = {
값: 1,
다음: {
값: 2,
다음: {
값: 3,
다음: {
값: 4,
다음: null
}
}
}
};
함수 printReverseList(목록) {
arr = [];
tmp = 목록을 보자;
동안(tmp) {
arr.push(tmp.value);
tmp = tmp.next;
}
for (let i = arr.length - 1; i >= 0; i--) {
경고( arr[i] );
}
}
printReverseList(목록);재귀 솔루션은 실제로 정확히 동일한 작업을 수행합니다. 즉, 목록을 따르고 (실행 컨텍스트 스택에서) 중첩 호출 체인의 항목을 기억한 다음 출력합니다.