JavaScript recursion_javascript 기술의 재귀 및 루프 예제 소개

재귀와 루프

반복적인 계산이 필요한 다양한 유형의 문제에 대해 루프와 재귀 방법은 각자의 장점이 있으며 보다 직관적이고 간단한 솔루션을 제공할 수 있습니다. 반면, 루프 방식과 재귀 방식은 서로 변환될 수 있습니다. 동일한 기능을 달성하기 위해 재귀를 사용하여 코드 루프를 다시 작성할 수 있습니다. 일반성을 잃지 않으면서 루프와 재귀는 다음 의사 코드를 사용하여 요약할 수 있습니다.

의사 코드 형식 설명: 루프는 while 형식을 채택하며 변수는 정의되지 않습니다. 할당은 조건식과 실행된 명령문을 함수 형식으로 작성하고 해당 값을 괄호 안에 작성합니다. 다른 구문 측면에서는 가능한 한 Javascript 사양에 가깝게 하십시오.

코드 복사 코드는 다음과 같습니다.

//루프의 의사 코드
// while form
function loop(arguments){
//결과의 초기값
result:=initial_value;

while(condition(변수, 인수)){/ /루프 조건 가능 인수만 필수이며 편의를 위해 루프 변수를 도입할 수도 있습니다
//계산 결과. 매개변수에는 이전 결과, 현재 루프 변수 및 외부 변수가 포함됩니다.
result:=calculate(result, Variable, extern_variables)
//함수의 외부 환경에 영향을 줍니다. 즉, 외부 변수를 수정합니다.
changeStatus( result, Variable , extern_variables);
//루프 본문의 명령문을 실행한 후 매개변수 또는 루프 변수를 수정합니다.
modify_arguments_variable(인수, 변수);
}
//Return result
return result;
}

마찬가지로 재귀 함수의 의사 코드를 제공합니다. .

코드 복사 코드는 다음과 같습니다.

//재귀의 의사 코드
함수 재귀(인수){
//다음 코드는 함수의 반복 호출을 제어하는 ​​구조 부분입니다.
//이 함수를 다시 호출하기 위한 새 매개변수를 가져옵니다. 이는 여러 인수 값 세트일 수 있습니다.
//루프의 조건(변수, 인수) 및 수정_인수_변수(인수, 변수)에 해당합니다.
new_arguments:=conditional_get_next(arguments);
//새 매개변수의 각 그룹에 대해 함수 자체를 호출합니다.
results:=recursion(new_arguments);

//다음 코드는 호출될 때마다 실행되는 기능적 부분입니다.
//결과를 계산합니다. 이전 결과, 현재 루프 변수 및 외부 변수가 포함됩니다.
//루프의 result:=calculate(result,variable,extern_variables)에 해당합니다.
result:=calculate(arguments, extern_variables);
result:=combine(result, results);
//함수의 외부 환경에 영향을 줍니다. 즉, 외부 변수를 수정합니다.
changeStatus (result,argers,extern_variables);
return result;
}

두 코드를 비교해 보면 루프와 재귀의 순서가 비슷하다는 것을 알 수 있습니다. 적절한 변환을 통해 모든 루프를 재귀적으로 구현할 수 있습니다. 이 변환은 프로그램이 단순할 때 쉽게 볼 수 있습니다. 예를 들어 다음과 같은 단순 누적 합계 함수는 다음과 같습니다.

코드 복사 코드는 다음과 같습니다.

// 루프
함수 sum(num){
var result=1;
while(num>1){
result =num
}
결과 반환
}

해당 재귀 형식:

코드 복사 코드는 다음과 같습니다.

//recursion
function sum2(num){
if (num>1){
return num sum(num-1); 🎜>}else {
return 1;
}
}


반대로, 대부분의 재귀 프로그램은 루프로 직접 구현할 수도 있습니다. 다음은 최대 공약수를 구하는 루프 형태의 함수입니다.

코드 복사 코드는 다음과 같습니다.

function gcd2(a, b){

var temp;
if (aa=b;
b=temp;
while (c!==0){
a=b;
b=c;
c=a%b;
return b; 🎜>

그러나 재귀에서 반복으로의 전환이 항상 쉬운 것은 아닙니다. 이 함수를 다시 호출하기 위해 새 인수를 생성하는 재귀 의사 코드의 부분

new_arguments:=conditional_get_next(arguments)

은 루프의 해당 부분보다 더 유연합니다. 재귀는 새로 생성된 매개변수 그룹의 수에 따라 두 가지 범주로 나눌 수 있습니다(함수에 필요한 모든 매개변수는 하나의 그룹입니다). 첫 번째 유형은 매개변수 그룹의 수가 고정되어 있고 재귀가 피보나치 수열과 최대 공약수 예시와 같은 루프로 변환될 수 있는 경우입니다. 두 번째 유형은 매개변수 그룹의 수가 불확실한 경우입니다. 그래프나 트리를 탐색할 때 각 점에는 임의 개수의 인접 점이 있습니다. 이 재귀는 루프로 직접 변환될 수 없습니다.

루프는 1차원 반복만 할 수 있는 반면 재귀는 2차원 구조를 순회할 수 있기 때문입니다. 예를 들어, 트리에서 노드에는 동일한 수준의 하위 노드와 노드가 모두 있습니다. 단순한 1차원 루프는 양방향으로 이동할 수 없습니다.

그러나 일부 데이터 구조의 도움으로 노드 위치에 대한 일부 정보를 기억한다면 두 번째 유형의 재귀를 루프로 구현할 수도 있습니다.

위의 관찰에서 도출된 결론을 연습하기 위해 또 다른 예를 들어보겠습니다. HTML5는 주어진 클래스 값을 가진 모든 요소를 ​​반환하는 Document 및 Element에 대한 새로운 메소드 getElementsByClassName(names)를 정의합니다. Firefox 3을 포함한 일부 브라우저는 이미 이 방법을 지원합니다. 아래에서는 먼저 재귀적 방법을 사용하여 더 약한 버전을 제공한 다음 루프 방법을 사용하여 다시 작성합니다.

코드 복사 코드는 다음과 같습니다.

var getElementsByClass={};
//elem은 HTMLElement입니다.
//name은 단일 클래스 이름입니다.
//주어진 이름을 포함하는 elem 아래에 모든 클래스 속성이 있는 요소가 포함된 배열을 반환합니다.
getElementsByClass.recursion1=함수(elem , 이름){
var list=[];
function getElements(el){
if (el.className.split(' ').indexOf(name)>-1){
list.push(el);
}
for (var i=0, c=el.children; igetElements(c[i]); }
}
getElements(elem);
return list;
}


앞서 언급했듯이 루프에서 노드의 위치 정보를 기억하려면, 다음과 같은 메소드의 데이터 구조를 구현할 수 있는 함수가 필요합니다.

push(object) //객체를 작성합니다.

objectpop() //가장 최근에 작성된 객체를 읽고 데이터 구조에서 삭제합니다.

objectget() //데이터 구조의 내용을 변경하지 않고 가장 최근에 작성된 객체를 읽습니다.

스택은 바로 이러한 후입선출(Last In First Out) 데이터 구조입니다. Javascript의 Array 객체는 처음 두 메서드를 지원하며 여기에 세 번째 메서드를 추가할 수 있습니다.

루프 버전:

코드 복사 코드는 다음과 같습니다.

getElementsByClass .loop1 = function(elem, name){

//필요한 스택의 기초로 js 배열 사용
var stack = []
stack.get = function(){
return stack[stack.length - 1];
}

var list = []
//비즈니스 로직 부분을
함수에 넣습니다. testElem(el ){
if (el.className.split(' ').indexOf(name) > -1) {
list.push(el)
}
}
// 루트 요소 확인
testElem(elem);
//스택 초기화
stack.push({
pointer: elem,
num: 0
});
var parent, num, el;
while(true) {
parent = stack.get()
el = parent.pointer.children[parent.num]
if( el) { //트리의 더 깊은 계층에 진입
testElem(el);
stack.push({
pointer: el,
num: 0
}); }
else {//상위 레이어로 돌아갑니다
if (stack.pop().pointer === elem) {
break
}
else {
stack. get() .num = 1;
}
}
}

반환 목록
}


결론적으로 말하자면. 모든 루프는 재귀를 사용하여 구현할 수 있습니다. 모든 재귀는 루프를 사용하여 구현할 수 있습니다. 어떤 방법을 사용하는지는 특정 문제와 사용자의 선호도에 따라 어떤 아이디어가 더 편리하고 직관적인지에 따라 다릅니다.

효율성

성능 측면에서 재귀는 루프에 비해 이점이 없습니다. 여러 함수 호출로 인한 오버헤드 외에도 재귀로 인해 경우에 따라 불필요한 반복 계산이 발생할 수도 있습니다. 피보나치 수열을 계산하는 재귀 프로그램을 예로 들어 보겠습니다. 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)

다른 관점에서 보면 A(i)를 찾을 때 C(i)가 있다고 하자. 필요한 추가 수는 다음과 같습니다.

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

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

D(i)=C(i) 1이라고 하면

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

D(i)가 있습니다. )=D(i-1) D(i-1)

그래서 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>1

따라서 n이 클 경우 위에 주어진 루프를 사용하는 프로그램은 재귀를 사용하는 프로그램보다 훨씬 빠릅니다.

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

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

코드 복사 코드는 다음과 같습니다.

//암기로 재귀
기능 fibonacci4(n ){
var memory = []; //계산된 각 항목을 저장하는 데 사용됩니다.
function calc(n){
var result, p, q
if (n < 2; ) {
메모리[n] = n
return n;
}
else {
p = 메모리[n - 1] : calc(n - 1);
q = 메모리[n - 2] : calc(n - 2);
결과 = p
메모리[n] = 결과; 결과;
}
}
return calc(n)