JavaScript 재귀의 재귀 및 루프 예

반복적인 계산이 필요한 다양한 유형의 문제에 대해 루프 및 재귀 방법은 고유한 장점을 가지며 보다 직관적이고 간단한 솔루션을 제공할 수 있습니다. 관심 있는 분들을 위해 다음은 JavaScript 재귀 및 루프에 대한 자세한 소개입니다.

재귀와 루프 알아보기

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

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

코드는 다음과 같습니다.

//pseudo code of a loop 
//while形式 
function loop(arguments){ 
//结果的初始值 
result:=initial_value; 
while(condition(variable, arguments)){//循环条件，可能只需arguments，也可能为了方便引入循环变量 
//计算结果。参数包括之前的结果、当前循环变量和外部变量 
result:=calculate(result, variable, extern_variables); 
//影响函数的外部环境，即修改外部变量 
changeStatus(result, variable, extern_variables); 
//执行完循环体中的语句后，修改参数或循环变量。 
modify_arguments_variable(arguments, variable); 
} 
//返回结果 
return result; 
}

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

코드는 다음과 같습니다.

//pseudo code of a recursion 
function recursion(arguments){ 
//以下代码为控制函数重复调用的结构部分。 
//获得再次调用此函数的新的参数，可能为多组arguments值。 
//对应于循环中的condition(variable, arguments)和modify_arguments_variable(arguments, variable)。 
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, arguments, extern_variables); 
return result; 
}

두 코드를 비교해 보면 루프와 재귀의 구성이 유사하다는 것을 알 수 있습니다. 순서를 바꾸고 적절하게 변환하면 됩니다. 루프는 재귀 방법을 사용하여 달성할 수 있습니다. 이 변환은 프로그램이 단순할 때 쉽게 볼 수 있습니다. 예를 들어 다음과 같은 단순 누적 합계 함수:

코드는 다음과 같습니다.

//loop 
function sum(num){ 
var result=1; 
while (num>1){ 
result+=num; 
num--; 
} 
return result; 
}

해당 재귀 형식:
코드는 다음과 같습니다.

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

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

코드는 다음과 같습니다.

function gcd2(a, b){ 
var temp; 
if (a<b){ 
temp=a; 
a=b; 
b=temp; 
} 
var c=a%b; 
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为单个class名 
//返回包含elem下所有class属性包含给定名称的element的数组 
getElementsByClass.recursion1=function (elem, name){ 
var list=[]; 
function getElements(el){ 
if (el.className.split(' ').indexOf(name)>-1){ 
list.push(el); 
} 
for (var i=0, c=el.children; i<c.length; i++){ 
getElements(c[i]); 
} 
} 
getElements(elem); 
return list; 
}

위에서 언급한 것처럼 루프에서 노드의 위치 정보를 기억하기 위해서는 다음을 구현할 수 있는 데이터 구조가 필요합니다. 방법.

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

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

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

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

루프 버전:

코드는 다음과 같습니다.

getElementsByClass.loop1 = function(elem, name){ 
//use a js array as the basis of a needed stack 
var stack = []; 
stack.get = function(){ 
return stack[stack.length - 1]; 
} 
var list = []; 
//the business logic part. put the eligible element to the list. 
function testElem(el){ 
if (el.className.split(' ').indexOf(name) > -1) { 
list.push(el); 
} 
} 
//check the root element 
testElem(elem); 
//initialize the stack 
stack.push({ 
pointer: elem, 
num: 0 
}); 
var parent, num, el; 
while (true) { 
parent = stack.get(); 
el = parent.pointer.children[parent.num]; 
if (el) {//enter a deeper layer of the tree 
testElem(el); 
stack.push({ 
pointer: el, 
num: 0 
}); 
} 
else {//return to the upper layer 
if (stack.pop().pointer === elem) { 
break; 
} 
else { 
stack.get().num += 1; 
} 
} 
} 

return list; 
}

归纳起来。所有循环都可以用递归实现；所有递归都可以用循环实现。采用哪种方法，由具体问题下哪种思路更方便直观和使用者的喜好决定。

效率

性能方面，递归不比循环有优势。除了多次函数调用的开销，在某些情况下，递归还会带来不必要的重复计算。以计算斐波那契数列的递归程序为例。求第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

令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较大时，前面给出的采用循环的程序会比采用递归的程序快很多。

如上一节中的循环一样，递归中的这个缺陷也是可以弥补的。我们只需要记住已经计算出来的项，求较高项时，就可以直接读取以前的项。这种技术在递归中很普遍，被称为“存储”(memorization)。

下面是采用存储技术的求斐波那契数列的递归算法。

代码如下:

//recursion with memorization 
function fibonacci4(n){ 
var memory = []; //used to store each calculated item 
function calc(n){ 
var result, p, q; 
if (n < 2) { 
memory[n] = n; 
return n; 
} 
else { 
p = memory[n - 1] ? memory[n - 1] : calc(n - 1); 
q = memory[n - 2] ? memory[n - 2] : calc(n - 2); 
result = p + q; 
memory[n] = result; 
return result; 
} 
} 
return calc(n); 
}

更多JavaScript的递归之递归与循环示例介绍相关文章请关注PHP中文网！